「链表」专题 2：测试的链表程序
为了测试我们写的代码是否正确，我们需要自己写两个个方法，这两个方法对于调试代码来说是十分有帮助的。
编写辅助函数：通过一个数组创建一个链表
Java 代码：
public ListNode createLinkedList(int[] arr) {
if (arr.length == 0) {
return null;
}
ListNode head = new ListNode(arr[0]);
ListNode current = head;
// 把这个迭代想象成一个动画去理解，就很好理解了
for (int i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}对代码的说明：
1、先创建头结点，在把头结点设置为当前节点，然后开始遍历，几乎成为了一个套路；
2、current = current.next; 表示指针后移，模板代码；
3、用头结点就可以代表一个链表，所以返回的是 head。
注意：要考虑到数组为空的情况。
编写辅助函数：通过一个链表的头结点打印一个链表
Java 代码：
public void printLinkedList(ListNode head){
ListNode current = head;
while (current!=null){
System.out.printf("%d -> ",current.val);
current = current.next;
}
System.out.println("NULL");
}下面我们在 main 函数中测试一下。
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
Solution solution = new Solution();
ListNode list1 = solution.createLinkedList(arr);
solution.printLinkedList(list1);
ListNode list2 = solution.reverseList(list1);
solution.printLinkedList(list2);
}练习
练习1：「力扣」第 83 题：从一个有序的列表中删除重复的元素
传送门：删除排序链表中的重复元素。
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2 输出: 1->2示例 2:
输入: 1->1->2->3->3 输出: 1->2->3
思路：有序链表，相同元素最多保留 $1$ 个。
Python 代码：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
# 【判断的条件是"下一个结点"】
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 先判断极端条件
if head is None or head.next is None:
return head
cur = head
while cur.next:
next = cur.next
if next.val == cur.val:
# q 向后挪动一位
cur.next = next.next
next.next = None
else:
cur = cur.next
return head练习2：「力扣」第 86 题：分割链表
英文网址：86. Partition List ，中文网址：86. 分隔链表。
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
思路：分别拿两个虚拟头结点，最后拼在一起。
Java 代码：
public class Solution2 {
// 空间复杂度为常数的解法：穿针引线
public ListNode partition(ListNode head, int x) {
// 比 x 小的虚拟头结点
ListNode dummyNodeL = new ListNode(-1);
// 大于等于 x 的虚拟头结点
ListNode dummyNodeR = new ListNode(-1);
// 用于遍历
ListNode curL = dummyNodeL;
// 用于遍历
ListNode curR = dummyNodeR;
int val;
while (head != null) {
val = head.val;
if (val < x) {
curL.next = head;
curL = curL.next;
} else {
curR.next = head;
curR = curR.next;
}
head = head.next;
}
curL.next = dummyNodeR.next;
// 特别注意：最后这一步不能忘记，否则会产生一个循环链表
curR.next = null;
return dummyNodeL.next;
}
public static void main(String[] args) {
int[] nums = {1, 4, 3, 2, 5, 2};
int x = 3;
ListNode head = new ListNode(nums);
Solution2 solution2 = new Solution2();
System.out.println("分隔链表之后：");
ListNode partition = solution2.partition(head, x);
System.out.println(partition);
}
}练习3：「力扣」第 328 题：奇数（Odd）偶数（Even）链表
传送门：英文网址：328. Odd Even Linked List ，中文网址：328. 奇偶链表 。
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL示例 2:
输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
思路：题目要求原地算法完成，那么就一定得“穿针引线”了。
- 方法1：可以使用 LeetCode 第 86 题题解思路 2 完成。
- 方法2：同样使用两个指针，一次跳过一个节点完成“穿针引线”，特别注意要一些边界情况的判断。
Python 代码：
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
# odd 奇数
odd_head = head
even_head = head.next
odd_cur = odd_head
even_cur = even_head
while even_cur and even_cur.next:
odd_cur.next = odd_cur.next.next
even_cur.next = even_cur.next.next
odd_cur = odd_cur.next
even_cur = even_cur.next
odd_cur.next = even_head
return odd_head我还写过一个题解在这里，可以参考一下。
练习4：「力扣」第 2 题：两个数相加
传送门：英文网址：2. Add Two Numbers ，中文网址：2. 两数相加 。
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
思路：需要考虑的问题：
1、数字中是否有前置的 $0$（除了 $0$ 以外，没有前置的 $0$）；
2、负数是否考虑。
编码过程中需要思考的问题：
1、如何分别获得这个数组的个位、十位、百位、千位；
2、分别相加，如果大于 $10$，进一。
Python 代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 is None:
return l2
if l2 is None:
return l1
dummy_node = ListNode(-1)
cur_node = dummy_node
s = 0
# 只要二者之一非空，就加下去
while l1 or l2:
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
cur_node.next = ListNode(s % 10)
s //= 10
cur_node = cur_node.next
if s == 1:
cur_node.next = ListNode(1)
return dummy_node.next练习5：「力扣」第 445 题：两个数相加
传送门：英文网址：445. Add Two Numbers II ，中文网址：445. 两数相加 II 。
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
思路：需要考虑的问题是如果不允许修改输入的链表该怎么办；使用一个辅助的数据结构来完成。
Python 代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
stack1 = []
stack2 = []
p1 = l1
p2 = l2
while p1:
stack1.append(p1.val)
p1 = p1.next
while p2:
stack2.append(p2.val)
p2 = p2.next
res = []
s = 0
while stack1 or stack2:
if stack1:
s += stack1.pop()
if stack2:
s += stack2.pop()
res.append(s % 10)
s //= 10
if s == 1:
res.append(1)
head = ListNode(res.pop())
cur_node = head
while len(res):
cur_node.next = ListNode(res.pop())
cur_node = cur_node.next
return head（本节完）
