知識點總結(jié)
1诅妹、鏈表問題只要涉及到頭結(jié)點的操作的，一般都會用到設置虛擬頭結(jié)點這個技巧；
2吭狡、鏈表中的問題尖殃，很多可以歸結(jié)為“穿針引線”，“穿針引線”要寫正確的一個重要技巧就是“畫圖”划煮，“畫圖”會使自己的思路更加清晰送丰，這一點是非常重要的；
3弛秋、鏈表中可以遞歸處理的問題有：（1）合并有序鏈表蚪战；（2）刪除鏈表中的結(jié)點；（3）反轉(zhuǎn)鏈表铐懊；（4）兩兩交換鏈表中的結(jié)點邀桑。
4、有的時候科乎，鏈表的操作壁畸，有循環(huán)或者判斷的，一定要記得看一看循環(huán)或者判斷的循環(huán)體或者判斷邏輯茅茂，就能檢查出自己的代碼是否寫得正確捏萍，例如 LeetCode 第 148 題，使用“歸并排序”將單鏈表進行排序和“單鏈表找中點”空闲。
下面這句話不一定對令杈，暫且先放在這里：鏈表的動態(tài)特性，很適合用來實現(xiàn)棧碴倾。數(shù)組適合在尾部操作逗噩，要擴容、縮容跌榔。鏈表適合在頭部操作异雁，每次都要 new 一個內(nèi)存空間。所以僧须，其實不論是數(shù)組實現(xiàn)還是鏈表實現(xiàn)纲刀，都沒有本質(zhì)區(qū)別。
反轉(zhuǎn)鏈表
LeetCode 第 206 題：反轉(zhuǎn)鏈表
LeetCode 第 92 題：反轉(zhuǎn)從位置 m 到 n 的鏈表担平，k 個組進行一次反轉(zhuǎn)
穿針引線示绊。
LeetCode 第 86 題：分割鏈表
不難，不過一直搞不清楚這個問題的意思暂论。
LeetCode 第 2 題面褐、第 445 題：鏈表求和
LeetCode 第 2 題：兩數(shù)相加
要求：給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中空另，它們各自的位數(shù)是按照 逆序 的方式存儲的盆耽，并且它們的每個節(jié)點只能存儲 一位 數(shù)字蹋砚。
如果扼菠，我們將這兩個數(shù)相加起來摄杂，則會返回一個新的鏈表來表示它們的和。
您可以假設除了數(shù)字 0 之外循榆，這兩個數(shù)都不會以 0 開頭析恢。
分析：這道題其實不難，主要考察了代碼的編寫能力秧饮。
1映挂、首先應該考慮到邊界情況：
if l1 is None:
return l2
if l2 is None:
return l1
2、鏈表問題一般都會設置虛擬頭結(jié)點盗尸；
3柑船、進位問題有模板寫法：模 得到位數(shù)，再除以
得到進位泼各；
4鞍时、最后考慮要不要進位 。
# Definition for singly-linked list.
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
問題并不難逆巍，但是編碼上要注意。轉(zhuǎn)換成數(shù)字不是不可以莽使，但是鏈表很長的時候锐极，就有越界的風險。
思考為什么要使用虛擬頭結(jié)點芳肌，計算 carry 是一個常見的關(guān)于進位的操作灵再。第 445 題稍微復雜，要借助棧完成亿笤。
LeetCode 第 445 題：兩數(shù)相加 II
傳送門：445. 兩數(shù)相加 II檬嘀。
刪除鏈表中等于給定值 val 的所有結(jié)點
LeetCode 第 203 題：刪除鏈表中等于給定值 val 的所有結(jié)點
一個對于鏈表常用的操作就是設置虛擬頭結(jié)點。
LeetCode 第 203 題：移除鏈表元素
傳送門：移除鏈表元素责嚷。
只要涉及跟鏈表頭結(jié)點有關(guān)的鸳兽，都要設計虛擬頭結(jié)點來避免繁瑣的討論。
LeetCode 第 82 題
傳送門：刪除排序鏈表中的重復元素 II罕拂。
LeetCode 第 83 題
傳送門：刪除排序鏈表中的重復元素揍异。
和 82 題完全不同。
分析：這道題給出兩種解法爆班。
相同之處：
- 都使用了當前指針和當前指針的下一指針衷掷，一共兩個指針來幫助我們完成邏輯。
- 當前指針的下一指針和"當前指針"作判斷柿菩，如果一樣戚嗅，說明應該丟棄"當前指針的下一指針"，如果一樣，說明應該保留"當前指針的下一指針"懦胞。
不同之處在于如何保留： - 發(fā)現(xiàn)一樣的元素的時候替久，馬上把 next 指針后移；
- 發(fā)現(xiàn)一樣的元素的時候躏尉，馬上把 current 指針挪到 next 指針的下一位蚯根。
關(guān)鍵點：
- 保證在遍歷過程中保持循環(huán)不變量的定義：current 總是指向第 1 次出現(xiàn)該數(shù)組的位置，next 用于遍歷胀糜，會走過所有的元素颅拦。
解法1：
提示：要考慮到一些特殊情況，才能寫好邏輯教藻。
public class Solution2 {
/**
* 從一個有序的鏈表中刪除重復的元素
* 思路：從后面往前面看距帅，有重復就刪除
*
* @param head
* @return
*/
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode cur = head;
ListNode next = cur.next;
while (next!=null){
if(next.val == cur.val){ // 1,1,1,1,2,3
// next 后移一位
next = next.next;
}else { // 1,2,3
cur.next = next; // 把 cur 的指針指向下一位
cur = next; // 移動指針
next = next.next;
}
}
// 這一行是一個要小心的陷阱
cur.next = null;
return head;
}
public static void main(String[] args) {
ListNode head1 = createListNode(new int[]{1,1,2,2,2,2,3,3,3,3});
Solution2 solution2 = new Solution2();
ListNode head2 = solution2.deleteDuplicates(head1);
printLinkedList(head2);
}
public static ListNode createListNode(int[] nums) {
if (nums.length == 0) {
return null;
}
ListNode head = new ListNode(nums[0]);
ListNode curNode = head;
for (int i = 1; i < nums.length; i++) {
curNode.next = new ListNode(nums[i]);
curNode = curNode.next;
}
return head;
}
// 超級簡單的一個工具方法
public static void printLinkedList(ListNode head) {
ListNode curNode = head;
while (curNode != null) {
System.out.printf("%s\t", curNode.val);
curNode = curNode.next;
}
System.out.printf("null");
}
}
解法2
public class Solution3 {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head;
ListNode next = cur.next;
while (next != null) {
if (next.val == cur.val) { // 1,1,2
// 因為 next 不被使用了，所以 cur 的下一個就指向 next 的下一個
cur.next = next.next;
// 此時不能移動 cur括堤，因為 cur 一定是第 1 個出現(xiàn)的元素锥债，注意這里保持循環(huán)不變量的定義
next = next.next;
} else { // 1,2,3
cur = next;
next = next.next;
}
}
return head;
}
public static void main(String[] args) {
ListNode head1 = createListNode(new int[]{1, 1, 2, 2, 2, 2, 3, 3, 3, 3});
Solution3 solution3 = new Solution3();
ListNode head2 = solution3.deleteDuplicates(head1);
printLinkedList(head2);
}
public static ListNode createListNode(int[] nums) {
if (nums.length == 0) {
return null;
}
ListNode head = new ListNode(nums[0]);
ListNode curNode = head;
for (int i = 1; i < nums.length; i++) {
curNode.next = new ListNode(nums[i]);
curNode = curNode.next;
}
return head;
}
// 超級簡單的一個工具方法
public static void printLinkedList(ListNode head) {
ListNode curNode = head;
while (curNode != null) {
System.out.printf("%s\t", curNode.val);
curNode = curNode.next;
}
System.out.printf("null");
}
}
LeetCode 第 328 題：奇數(shù)（Odd）偶數(shù)（Even）鏈表
傳送門： https://leetcode.com/problems/odd-even-linked-list/description/
思路：在遍歷的過程中，標記奇數(shù)節(jié)點和偶數(shù)節(jié)點痊臭，把奇數(shù)節(jié)點和偶數(shù)節(jié)點分開哮肚。最后把奇數(shù)節(jié)點的最后一個節(jié)點指向偶數(shù)節(jié)點的開始節(jié)點，具體細節(jié)請見代碼广匙。
我的解答：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode oddHead = head;
ListNode evenHead = oddHead.next;
ListNode oddNode = oddHead;
ListNode evenNode = evenHead;
ListNode currentNode = evenHead.next;
boolean isodd = true;
while (currentNode != null) {
if (isodd) {
oddNode.next = currentNode;
oddNode = currentNode;
} else {
evenNode.next = currentNode;
evenNode = currentNode;
}
isodd = !isodd;
currentNode = currentNode.next;
}
isodd = !isodd;
if (isodd) {
oddNode.next = evenHead;
evenNode.next = null;
} else {
oddNode.next = evenHead;
}
return oddHead;
}
public static void main(String[] args) {
ListNode node1 = createListNode(new int[]{1, 2, 3, 4, 5});
Solution solution = new Solution();
ListNode result1 = solution.oddEvenList(node1);
printLinkedList(result1);
System.out.println("------");
ListNode node2 = createListNode(new int[]{1, 2, 3, 4});
ListNode result2 = solution.oddEvenList(node2);
printLinkedList(result2);
System.out.println("------");
ListNode node3 = createListNode(new int[]{1, 2});
ListNode result3 = solution.oddEvenList(node3);
printLinkedList(result3);
}
public static ListNode createListNode(int[] nums) {
if (nums.length == 0) {
return null;
}
ListNode head = new ListNode(nums[0]);
ListNode curNode = head;
for (int i = 1; i < nums.length; i++) {
curNode.next = new ListNode(nums[i]);
curNode = curNode.next;
}
return head;
}
// 超級簡單的一個工具方法
public static void printLinkedList(ListNode head) {
ListNode curNode = head;
while (curNode != null) {
System.out.printf("%s\t", curNode.val);
curNode = curNode.next;
}
System.out.printf("null");
}
}
網(wǎng)友的解答：http://blog.csdn.net/guicaisa/article/details/50557475
顯然允趟，網(wǎng)友的解法會更簡潔一些：
根據(jù)網(wǎng)友的解答自己寫了一遍：
public class Solution2 {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode oddNode = head;
ListNode evenNode = head.next;
ListNode evenHead = evenNode;
while (evenNode != null && evenNode.next != null) {
oddNode.next = evenNode.next;
oddNode = oddNode.next;
evenNode.next = oddNode.next;
evenNode = evenNode.next;
}
oddNode.next = evenHead;
return head;
}
public static void main(String[] args) {
ListNode node1 = createListNode(new int[]{1, 2, 3, 4, 5});
Solution2 solution = new Solution2();
ListNode result1 = solution.oddEvenList(node1);
printLinkedList(result1);
System.out.println("------");
ListNode node2 = createListNode(new int[]{1, 2, 3, 4});
ListNode result2 = solution.oddEvenList(node2);
printLinkedList(result2);
System.out.println("------");
ListNode node3 = createListNode(new int[]{1, 2});
ListNode result3 = solution.oddEvenList(node3);
printLinkedList(result3);
}
public static ListNode createListNode(int[] nums) {
if (nums.length == 0) {
return null;
}
ListNode head = new ListNode(nums[0]);
ListNode curNode = head;
for (int i = 1; i < nums.length; i++) {
curNode.next = new ListNode(nums[i]);
curNode = curNode.next;
}
return head;
}
// 超級簡單的一個工具方法
public static void printLinkedList(ListNode head) {
ListNode curNode = head;
while (curNode != null) {
System.out.printf("%s\t", curNode.val);
curNode = curNode.next;
}
System.out.printf("null");
}
}
LeetCode 第 147 題：單鏈表的插入排序
重刷
LeetCode 第 148 題：單鏈表的排序，使用歸并排序
LeetCode 第 24 題：兩兩交換鏈表中的結(jié)點
LeetCode 第 25 題：k 個一組交換鏈表
重刷
LeetCode 第 138 題：復制帶隨機指針的鏈表
LeetCode 第 109 題：有序鏈表轉(zhuǎn)換二叉搜索樹
英文網(wǎng)址：109. Convert Sorted List to Binary Search Tree 鸦致，中文網(wǎng)址：109. 有序鏈表轉(zhuǎn)換二叉搜索樹 潮剪。
LeetCode 第 237 題：刪除鏈表中的結(jié)點
要求：請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾的）結(jié)點分唾，您將只被給予要求被刪除的結(jié)點抗碰。
LeetCode 第 21 題：合并兩個有序鏈表
LeetCode 第 21 題：合并兩個有序鏈表
使用遞歸解決穿針引線，單雙轉(zhuǎn)換
穿針引線：
image-20190111135807481
遞歸寫法：首先先寫好遞歸終止條件绽乔。
image-20190111135825172
LeetCode 第 23 題：合并 K 個排序鏈表
英文網(wǎng)址：23. Merge k Sorted Lists 弧蝇，中文網(wǎng)址：23. 合并K個排序鏈表 。
分析：歸并多個有序鏈表（多路歸并排序）折砸，要用到優(yōu)先隊列
LeetCode 第 19 題：刪除鏈表的倒數(shù)第 N 個結(jié)點
LeetCode 第 61 題：旋轉(zhuǎn)鏈表
LeetCode 第 143 題：重排鏈表
LeetCode 第 234 題：回文鏈表
LeetCode 第 141 題：找出鏈表中是否有環(huán)
LeetCode 第 142 題：找出鏈表的入口結(jié)點
LeetCode 第 114 題：二叉樹展開為鏈表
要求：給定一個二叉樹看疗，原地將它展開為鏈表。
例如睦授，給定二叉樹
1
/ \
2 5
/ \ \
3 4 6
將其展開為：
1
\
2
\
3
\
4
\
5
\
6
Java 代碼：后序遍歷
class Solution {
public void flatten(TreeNode root) {
if(root == null){
return ;
}
flatten(root.left);
flatten(root.right);
if(root.left != null){
TreeNode right = root.right;//記錄右結(jié)點
root.right = root.left;
root.left = null;//將左結(jié)點置空
TreeNode node = root.right;//到左結(jié)點的最后一個結(jié)點
while(node.right != null){
node = node.right;
}
node.right = right;
}
}
}
鏈表的中間結(jié)點
LeetCode 第 876 題：單鏈表的一個常見操作两芳，設置快慢指針。
LeetCode 第 61 題：鏈表向右旋轉(zhuǎn)
傳送門：61. 旋轉(zhuǎn)鏈表去枷。
給定一個鏈表怖辆，旋轉(zhuǎn)鏈表是复，將鏈表每個節(jié)點向右移動 k 個位置，其中 k 是非負數(shù)竖螃。
示例 1:
輸入: 1->2->3->4->5->NULL, k = 2 輸出: 4->5->1->2->3->NULL 解釋: 向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL 向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL示例 2:
輸入: 0->1->2->NULL, k = 4 輸出: 2->0->1->NULL 解釋: 向右旋轉(zhuǎn) 1 步: 2->0->1->NULL 向右旋轉(zhuǎn) 2 步: 1->2->0->NULL 向右旋轉(zhuǎn) 3 步: 0->1->2->NULL 向右旋轉(zhuǎn) 4 步: 2->0->1->NULL
Python 代碼：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or k <= 0:
return head
# 先看鏈表有多少元素
node = head
# 先數(shù)這個鏈表的長度
counter = 1
while node.next:
node = node.next
counter += 1
node.next = head
k = k % counter
node = head
# counter - k - 1 可以取一些極端的例子找到規(guī)律
for _ in range(counter - k - 1):
node = node.next
new_head = node.next
node.next = None
return new_head
（本節(jié)完）
