知識(shí)點(diǎn)總結(jié)
1、鏈表問(wèn)題只要涉及到頭結(jié)點(diǎn)的操作的，一般都會(huì)用到設(shè)置虛擬頭結(jié)點(diǎn)這個(gè)技巧；
2、鏈表中的問(wèn)題，很多可以歸結(jié)為“穿針引線”，“穿針引線”要寫(xiě)正確的一個(gè)重要技巧就是“畫(huà)圖”，“畫(huà)圖”會(huì)使自己的思路更加清晰，這一點(diǎn)是非常重要的；
3、鏈表中可以遞歸處理的問(wèn)題有：（1）合并有序鏈表；（2）刪除鏈表中的結(jié)點(diǎn)；（3）反轉(zhuǎn)鏈表；（4）兩兩交換鏈表中的結(jié)點(diǎn)。
4、有的時(shí)候，鏈表的操作，有循環(huán)或者判斷的，一定要記得看一看循環(huán)或者判斷的循環(huán)體或者判斷邏輯，就能檢查出自己的代碼是否寫(xiě)得正確，例如 LeetCode 第 148 題，使用“歸并排序”將單鏈表進(jìn)行排序和“單鏈表找中點(diǎn)”。
下面這句話不一定對(duì)，暫且先放在這里：鏈表的動(dòng)態(tài)特性，很適合用來(lái)實(shí)現(xiàn)棧。數(shù)組適合在尾部操作，要擴(kuò)容、縮容。鏈表適合在頭部操作，每次都要 new 一個(gè)內(nèi)存空間。所以，其實(shí)不論是數(shù)組實(shí)現(xiàn)還是鏈表實(shí)現(xiàn)，都沒(méi)有本質(zhì)區(qū)別。
反轉(zhuǎn)鏈表
LeetCode 第 206 題：反轉(zhuǎn)鏈表
LeetCode 第 92 題：反轉(zhuǎn)從位置 m 到 n 的鏈表，k 個(gè)組進(jìn)行一次反轉(zhuǎn)
穿針引線。
LeetCode 第 86 題：分割鏈表
不難，不過(guò)一直搞不清楚這個(gè)問(wèn)題的意思。
LeetCode 第 2 題、第 445 題：鏈表求和
LeetCode 第 2 題：兩數(shù)相加
要求：給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。
分析：這道題其實(shí)不難，主要考察了代碼的編寫(xiě)能力。
1、首先應(yīng)該考慮到邊界情況：
if l1 is None:
return l2
if l2 is None:
return l1
2、鏈表問(wèn)題一般都會(huì)設(shè)置虛擬頭結(jié)點(diǎn)；
3、進(jìn)位問(wèn)題有模板寫(xiě)法：模 得到位數(shù)，再除以
得到進(jìn)位；
4、最后考慮要不要進(jìn)位 。
# 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
問(wèn)題并不難，但是編碼上要注意。轉(zhuǎn)換成數(shù)字不是不可以，但是鏈表很長(zhǎng)的時(shí)候，就有越界的風(fēng)險(xiǎn)。
思考為什么要使用虛擬頭結(jié)點(diǎn)，計(jì)算 carry 是一個(gè)常見(jiàn)的關(guān)于進(jìn)位的操作。第 445 題稍微復(fù)雜，要借助棧完成。
LeetCode 第 445 題：兩數(shù)相加 II
傳送門(mén)：445. 兩數(shù)相加 II。
刪除鏈表中等于給定值 val 的所有結(jié)點(diǎn)
LeetCode 第 203 題：刪除鏈表中等于給定值 val 的所有結(jié)點(diǎn)
一個(gè)對(duì)于鏈表常用的操作就是設(shè)置虛擬頭結(jié)點(diǎn)。
LeetCode 第 203 題：移除鏈表元素
傳送門(mén)：移除鏈表元素。
只要涉及跟鏈表頭結(jié)點(diǎn)有關(guān)的，都要設(shè)計(jì)虛擬頭結(jié)點(diǎn)來(lái)避免繁瑣的討論。
LeetCode 第 82 題
傳送門(mén)：刪除排序鏈表中的重復(fù)元素 II。
LeetCode 第 83 題
傳送門(mén)：刪除排序鏈表中的重復(fù)元素。
和 82 題完全不同。
分析：這道題給出兩種解法。
相同之處：
- 都使用了當(dāng)前指針和當(dāng)前指針的下一指針，一共兩個(gè)指針來(lái)幫助我們完成邏輯。
- 當(dāng)前指針的下一指針和"當(dāng)前指針"作判斷，如果一樣，說(shuō)明應(yīng)該丟棄"當(dāng)前指針的下一指針"，如果一樣，說(shuō)明應(yīng)該保留"當(dāng)前指針的下一指針"。
不同之處在于如何保留： - 發(fā)現(xiàn)一樣的元素的時(shí)候，馬上把 next 指針后移；
- 發(fā)現(xiàn)一樣的元素的時(shí)候，馬上把 current 指針挪到 next 指針的下一位。
關(guān)鍵點(diǎn)：
- 保證在遍歷過(guò)程中保持循環(huán)不變量的定義：current 總是指向第 1 次出現(xiàn)該數(shù)組的位置，next 用于遍歷，會(huì)走過(guò)所有的元素。
解法1：
提示：要考慮到一些特殊情況，才能寫(xiě)好邏輯。
public class Solution2 {
/**
* 從一個(gè)有序的鏈表中刪除重復(fù)的元素
* 思路：從后面往前面看，有重復(fù)就刪除
*
* @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; // 移動(dòng)指針
next = next.next;
}
}
// 這一行是一個(gè)要小心的陷阱
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;
}
// 超級(jí)簡(jiǎn)單的一個(gè)工具方法
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
// 因?yàn)?next 不被使用了，所以 cur 的下一個(gè)就指向 next 的下一個(gè)
cur.next = next.next;
// 此時(shí)不能移動(dòng) cur，因?yàn)?cur 一定是第 1 個(gè)出現(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;
}
// 超級(jí)簡(jiǎn)單的一個(gè)工具方法
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）鏈表
傳送門(mén)： https://leetcode.com/problems/odd-even-linked-list/description/
思路：在遍歷的過(guò)程中，標(biāo)記奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)，把奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分開(kāi)。最后把奇數(shù)節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)指向偶數(shù)節(jié)點(diǎn)的開(kāi)始節(jié)點(diǎn)，具體細(xì)節(jié)請(qǐng)見(jiàn)代碼。
我的解答：
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;
}
// 超級(jí)簡(jiǎn)單的一個(gè)工具方法
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)友的解法會(huì)更簡(jiǎn)潔一些：
根據(jù)網(wǎng)友的解答自己寫(xiě)了一遍：
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;
}
// 超級(jí)簡(jiǎn)單的一個(gè)工具方法
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 題：?jiǎn)捂湵淼牟迦肱判?/h3>
重刷
LeetCode 第 148 題：?jiǎn)捂湵淼呐判?，使用歸并排序
LeetCode 第 24 題：兩兩交換鏈表中的結(jié)點(diǎn)
LeetCode 第 25 題：k 個(gè)一組交換鏈表
重刷
LeetCode 第 138 題：復(fù)制帶隨機(jī)指針的鏈表
LeetCode 第 109 題：有序鏈表轉(zhuǎn)換二叉搜索樹(shù)
英文網(wǎng)址：109. Convert Sorted List to Binary Search Tree ，中文網(wǎng)址：109. 有序鏈表轉(zhuǎn)換二叉搜索樹(shù) 。
LeetCode 第 237 題：刪除鏈表中的結(jié)點(diǎn)
要求：請(qǐng)編寫(xiě)一個(gè)函數(shù)，使其可以刪除某個(gè)鏈表中給定的（非末尾的）結(jié)點(diǎn)，您將只被給予要求被刪除的結(jié)點(diǎn)。
LeetCode 第 21 題：合并兩個(gè)有序鏈表
LeetCode 第 21 題：合并兩個(gè)有序鏈表
使用遞歸解決穿針引線，單雙轉(zhuǎn)換
穿針引線：
遞歸寫(xiě)法：首先先寫(xiě)好遞歸終止條件。
LeetCode 第 23 題：合并 K 個(gè)排序鏈表
英文網(wǎng)址：23. Merge k Sorted Lists ，中文網(wǎng)址：23. 合并K個(gè)排序鏈表 。
分析：歸并多個(gè)有序鏈表（多路歸并排序），要用到優(yōu)先隊(duì)列
LeetCode 第 19 題：刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
LeetCode 第 61 題：旋轉(zhuǎn)鏈表
LeetCode 第 143 題：重排鏈表
LeetCode 第 234 題：回文鏈表
LeetCode 第 141 題：找出鏈表中是否有環(huán)
LeetCode 第 142 題：找出鏈表的入口結(jié)點(diǎn)
LeetCode 第 114 題：二叉樹(shù)展開(kāi)為鏈表
要求：給定一個(gè)二叉樹(shù)，原地將它展開(kāi)為鏈表。
例如，給定二叉樹(shù)
1
/ \
2 5
/ \ \
3 4 6
將其展開(kāi)為：
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é)點(diǎn)
root.right = root.left;
root.left = null;//將左結(jié)點(diǎn)置空
TreeNode node = root.right;//到左結(jié)點(diǎn)的最后一個(gè)結(jié)點(diǎn)
while(node.right != null){
node = node.right;
}
node.right = right;
}
}
}
鏈表的中間結(jié)點(diǎn)
LeetCode 第 876 題：?jiǎn)捂湵淼囊粋€(gè)常見(jiàn)操作，設(shè)置快慢指針。
LeetCode 第 61 題：鏈表向右旋轉(zhuǎn)
傳送門(mén)：61. 旋轉(zhuǎn)鏈表。
給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(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ù)這個(gè)鏈表的長(zhǎng)度
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é)完）
