為了測試我們寫的代碼是否正確，我們需要自己寫兩個個方法，這兩個方法對于調試代碼來說是十分有幫助的。
編寫輔助函數(shù)：通過一個數(shù)組創(chuàng)建一個鏈表
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、先創(chuàng)建頭結點，在把頭結點設置為當前節(jié)點，然后開始遍歷，幾乎成為了一個套路；
2、current = current.next; 表示指針后移，模板代碼；
3、用頭結點就可以代表一個鏈表，所以返回的是 head。
注意：要考慮到數(shù)組為空的情況。
編寫輔助函數(shù)：通過一個鏈表的頭結點打印一個鏈表
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 函數(shù)中測試一下。
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：LeetCode 第 83 題：從一個有序的列表中刪除重復的元素
傳送門：刪除排序鏈表中的重復元素。
給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2 輸出: 1->2示例 2:
輸入: 1->1->2->3->3 輸出: 1->2->3
思路：有序鏈表，相同元素最多保留 個。
Python 代碼：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# 給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現(xiàn)一次。
# 【判斷的條件是"下一個結點"】
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：LeetCode 第 86 題：分割鏈表
英文網(wǎng)址：86. Partition List ，中文網(wǎng)址：86. 分隔鏈表 。
給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。
你應當保留兩個分區(qū)中每個節(jié)點的初始相對位置。
示例:
輸入: head = 1->4->3->2->5->2, x = 3 輸出: 1->2->2->4->3->5
思路：分別拿兩個虛擬頭結點，最后拼在一起。
Java 代碼：
public class Solution2 {
// 空間復雜度為常數(shù)的解法：穿針引線
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;
// 特別注意：最后這一步不能忘記，否則會產生一個循環(huán)鏈表
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：LeetCode 第 328 題：奇數(shù)（Odd）偶數(shù)（Even）鏈表
傳送門：英文網(wǎng)址：328. Odd Even Linked List ，中文網(wǎng)址：328. 奇偶鏈表 。
給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節(jié)點總數(shù)。
示例 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說明:
- 應當保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序。
- 鏈表的第一個節(jié)點視為奇數(shù)節(jié)點，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推。
思路：題目要求原地算法完成，那么就一定得“穿針引線”了。
- 方法1：可以使用 LeetCode 第 86 題題解思路 2 完成。
- 方法2：同樣使用兩個指針，一次跳過一個節(jié)點完成“穿針引線”，特別注意要一些邊界情況的判斷。
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 奇數(shù)
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：LeetCode 第 2 題：兩個數(shù)相加
傳送門：英文網(wǎng)址：2. Add Two Numbers ，中文網(wǎng)址：2. 兩數(shù)相加 。
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出：7 -> 0 -> 8 原因：342 + 465 = 807
思路：需要考慮的問題：1、數(shù)字中是否有前置的0（除了0以外，沒有前置的0）；2、負數(shù)是否考慮。
編碼過程中需要思考的問題：1、如何分別獲得這個數(shù)組的個位、十位、百位、千位；2、分別相加，如果大于 ，進一。
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：LeetCode 第 445 題：兩個數(shù)相加
傳送門：英文網(wǎng)址：445. Add Two Numbers II ，中文網(wǎng)址：445. 兩數(shù)相加 II 。
給定兩個非空鏈表來代表兩個非負整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個節(jié)點只存儲單個數(shù)字。將這兩數(shù)相加會返回一個新的鏈表。
你可以假設除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
進階:
如果輸入鏈表不能修改該如何處理？換句話說，你不能對列表中的節(jié)點進行翻轉。
示例:
輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出: 7 -> 8 -> 0 -> 7
思路：需要考慮的問題是如果不允許修改輸入的鏈表該怎么辦；使用一個輔助的數(shù)據(jù)結構來完成。
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
（本節(jié)完）
