//leetcode中還有花樣鏈表題，這里幾個(gè)例子，冰山一角
- 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)----時(shí)間復(fù)雜度O（n）
這是最最基本的了，應(yīng)該能夠迅速寫(xiě)出正確的代碼，注意檢查鏈表是否為空。參考代碼如下：
public static int getListLength(Node head) {
// 注意頭結(jié)點(diǎn)為空情況
if (head == null) {
return 0;
}
int len = 0;
Node cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
return len;
}
- 將單鏈表反轉(zhuǎn)----時(shí)間復(fù)雜度O（n）(也可以先inplace的翻轉(zhuǎn)，再遍歷，空間復(fù)雜度降到O(1))
- 從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。
- 如果鏈表為空或只有一個(gè)節(jié)點(diǎn)，無(wú)需反轉(zhuǎn)，直接返回原鏈表表頭。
注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。參考代碼如下：
public static Node reverseList(Node head) {
if (head == null || head.next == null) {
return head;
}
Node reHead = null; // 反轉(zhuǎn)后新鏈表最前面的node
Node cur = head;
while (cur != null) {
Node preCur = cur; // 用preCur保存住對(duì)要處理節(jié)點(diǎn)的引用
cur = cur.next; // cur更新到下一個(gè)節(jié)點(diǎn)
preCur.next = reHead; // 更新當(dāng)前節(jié)點(diǎn)的next引用，當(dāng)前.next指向 翻轉(zhuǎn)后鏈表最前面的node ==>當(dāng)前節(jié)點(diǎn)成為翻轉(zhuǎn)后鏈表最前面的node
reHead = preCur; // reHead更新
}
return reHead;
}
- leetcode例題
206. Reverse LinkedList
沒(méi)做過(guò)一上來(lái)感覺(jué)不太好想，有個(gè)視頻，看到一半恍然大悟：https://www.youtube.com/watch?v=sYcOK51hl-A
這類(lèi)題都開(kāi)始要求用iteration寫(xiě)一次再用recursive寫(xiě)一個(gè)
//假設(shè)1->2->3->4,先從head=1開(kāi)始，要翻轉(zhuǎn)，最后一個(gè)會(huì)變成head，所以head一步一步向后挪，每一步也一起翻轉(zhuǎn)指向
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head!=null){
ListNode nextHead = head.next;
head.next = prev;
prev=head;
//這里得到的prev即下一個(gè)head前面的數(shù)，也就是下一個(gè)head要指向的數(shù)，當(dāng)head=最后一個(gè)node（tail）時(shí)，prev=tail，循環(huán)結(jié)束
head = nextHead;
}
return prev;
}
//recursive
public ListNode reverseList(ListNode head) {
return reverseRecursive(head,null);
}
public ListNode reverseRecursive(ListNode head,ListNode prev){
if(head==null) return prev;
ListNode nextHead = head.next;
head.next=prev;
//下面?zhèn)鲄⑵鋵?shí)就相當(dāng)于這兩句：prev=head;head = nextHead;
return reverseRecursive(nextHead,head);
}
}
92. Reverse Linked List II
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
根據(jù)題中的例子，第二個(gè)for循環(huán)開(kāi)始
loop1:
1 --> 2 --> 3 --> 4 --> 5 --> NULL
p c n
cur.next = next.next;
2 --> 4
next.next = prev.next;
3 --> 2
prev.next = next;
1 --> 3
==> 1 --> 3 --> 2 --> 4 --> 5 --> NULL
p c n
loop2:
cur.next = next.next;
2 --> 5
next.next = prev.next;
4 --> 3
prev.next = next;
1 --> 4
==> 1 --> 4 --> 3 --> 2 --> 5 --> NULL
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m == n) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode cur = head;
//在reverse之前的部分平移
for(int i = 0; i < m - 1; i++){
prev = prev.next;
cur = cur.next;
}
for(int i = 0; i < n - m; i++){
ListNode next = cur.next;
cur.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
- 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn)（k > 0）----時(shí)間復(fù)雜度O（n）
- 最普遍的方法是，先統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)，然后再找到第（n-k）個(gè)結(jié)點(diǎn)。注意鏈表為空，k為0，k為1，k大于鏈表中節(jié)點(diǎn)個(gè)數(shù)時(shí)這三種情況情況。代碼不寫(xiě)了。
- 另一個(gè)思路主要就是使用兩個(gè)指針，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)，這樣前后兩個(gè)指針的距離差是k-1，之后前后兩個(gè)指針一起向前走，前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)。
19. Remove Nth Node From End of List
walker and runner, init walker,runner both as dummy, move runner n steps, so that the gap between runner and walker =n, then move runner and walker together, when runner get to the end of List, walker is before the nth from the end node, walker.next=walke.next.next， skip original walker.next
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode walker = dummy;
ListNode runner = dummy;
// after for loop, gap between runner and walker =n
for(int i = 1; i <= n; i++){
runner = runner.next;
}
while(runner.next!=null){
runner = runner.next;
walker = walker.next;
}
walker.next=walker.next.next;//skip nth node
return dummy.next;
}
- 查找單鏈表的中間結(jié)點(diǎn)----時(shí)間復(fù)雜度O（n）
此題可應(yīng)用于上一題類(lèi)似的思想。也是設(shè)置兩個(gè)指針，只不過(guò)這里是，兩個(gè)指針同時(shí)向前走，walker one step each time，runner two steps each time，runner get to the end, walker==mid，即第（n/2+1）個(gè)結(jié)點(diǎn)。還是分三種情況：鏈表結(jié)點(diǎn)個(gè)數(shù)為1和2的情況和其他。
public static Node getMiddleNode(Node head) {
if (head == null || head.next == null) {
return head;
}
Node walker = head; ]
Node runner = head;
// 前面指針每次走兩步，直到指向最后一個(gè)結(jié)點(diǎn)，后面指針每次走一步
while (walker.next != null) {
walker = walker.next;
runner = runner.next;
if (runner.next != null) {
runner = runner.next;
}
}
return walker;
}
- 從尾到頭打印單鏈表----時(shí)間復(fù)雜度O（n）
對(duì)于這種顛倒順序的問(wèn)題，我們應(yīng)該就會(huì)想到棧，后進(jìn)先出。所以，這一題要么自己使用棧，要么讓系統(tǒng)使用棧，也就是遞歸。注意鏈表為空的情況。
public static void reversePrintListStack(Node head) {
Stack<Node> s = new Stack<Node>();
Node cur = head;
while (cur != null) {
s.push(cur);
cur = cur.next;
}
while (!s.empty()) {
cur = s.pop();
System.out.print(cur.val + " ");
}
}
/**
使用遞歸（優(yōu)雅?。? */
public static void reversePrintListRec(Node head) {
if (head == null) {
return;
} else {
reversePrintListRec(head.next);
System.out.print(head.val + " ");
}
}
- Merge two sorted linked list----時(shí)間復(fù)雜度為O（max(len1, len2)）,O（1）的空間
已知兩個(gè)單鏈表pHead1 和pHead2 各自有序，把它們合并成一個(gè)鏈表依然有序
這個(gè)類(lèi)似歸并排序。尤其注意兩個(gè)鏈表都為空，和其中一個(gè)為空時(shí)的情況。
21. Merge Two Sorted Lists
還是iteration和recursion,iteration代碼太長(zhǎng)了，由此可見(jiàn)遞歸的好處，代碼簡(jiǎn)介易懂
iteration注意 l1,l2挨個(gè)merge的時(shí)候?yàn)榱朔奖?，l1,l2在merge后指向自己next，即后移，同時(shí)head即新鏈表的當(dāng)前node也后移，另外這里也是head不確定的情況，所以用dummy
//recursion
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
//iteration
public static Node mergeSortedList(Node head1, Node head2) {
// 其中一個(gè)鏈表為空的情況，直接返回另一個(gè)鏈表頭，O(1)
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node mergeHead = null;
// 先確定下來(lái)mergeHead是在哪里
if (head1.val < head2.val) {
mergeHead = head1;
head1 = head1.next; // 跳過(guò)已經(jīng)合并了的元素，指向已merge的node的next
mergeHead.next = null; // 斷開(kāi)mergeHead和后面的聯(lián)系
} else {
mergeHead = head2;
head2 = head2.next;
mergeHead.next = null;
}
Node mergeCur = mergeHead;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
mergeCur.next = head1; // 把找到較小的元素合并到merge中
head1 = head1.next; // 跳過(guò)已經(jīng)合并了的元素
mergeCur = mergeCur.next; // 找到下一個(gè)準(zhǔn)備合并的元素
mergeCur.next = null; // 斷開(kāi)mergeCur和后面的聯(lián)系
} else {
mergeCur.next = head2;
head2 = head2.next;
mergeCur = mergeCur.next;
mergeCur.next = null;
}
}
// 合并剩余的元素，這個(gè)很重要，而且大部分merge算法最后都需要merge剩余東西這一步
if (head1 != null) {
mergeCur.next = head1;
} else if (head2 != null) {
mergeCur.next = head2;
}
return mergeHead;
}
23. Merge k Sorted Lists
根據(jù)priority queue的特性，我們可以通過(guò)重寫(xiě)compare方法利用priority queue實(shí)現(xiàn)，還有dummy，從后向前拼接。
和下面sort里179一樣，都重寫(xiě)了compare。一個(gè)是sort方法內(nèi)，一個(gè)是priority queue
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length==0) return null;
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
@Override
/*
1. 這里compare方法可以直接return n1.val-n2.val;
*/
public int compare(ListNode n1, ListNode n2){
if(n1.val<n2.val) return -1;
else if(n1.val==n2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for(ListNode n:lists){
if(n!=null) queue.add(n);
}
while(!queue.isEmpty()){
tail.next = queue.poll();
tail=tail.next;
if(tail.next!=null){
queue.add(tail.next)；
}
}
return dummy.next;
}
- 判斷一個(gè)單鏈表中是否有環(huán)----時(shí)間復(fù)雜度為O（n）
這里也是用到兩個(gè)指針。如果一個(gè)鏈表中有環(huán)，也就是說(shuō)用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的。因此，我們可以用兩個(gè)指針去遍歷，一個(gè)指針一次走兩步，一個(gè)指針一次走一步，如果有環(huán)，兩個(gè)指針肯定會(huì)在環(huán)中相遇。
141. Linked List Cycle
- 用雙指針的思路，walker moves step by step. runner moves two steps at time. if the Linked List has a cycle walker and runner will meet at some
point. - 解法代碼下一題中其實(shí)是包含的，但我還是把這個(gè)代碼貼出來(lái)了，因?yàn)榕卸l件那里需要注意，這道題的寫(xiě)法是，先判斷了head==null，之后while中判斷runner.next和runner.next.next，個(gè)人理解是runner跑的快，需要注意判斷runner而不是walker。下一題的寫(xiě)法看起來(lái)跟這個(gè)不同，其實(shí)一樣
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode walker = head;
ListNode runner = head;
// runner跑的快，在前面，所以判斷runner.next, runner.next.next
while(runner.next!=null&&runner.next.next!=null){
walker = walker.next;
runner = runner.next.next;
if(walker==runner) return true;
}
return false;
}
142. Linked List Cycle2
關(guān)于判定條件的一個(gè)問(wèn)題上道題中解釋了
這個(gè)題目的思路不太好想，discuss中有一個(gè)很好的解釋?zhuān)N過(guò)來(lái)，其中關(guān)鍵的兩點(diǎn)是，walker走過(guò)的距離和cycle長(zhǎng)度的關(guān)系，以及walker,runner相遇之后再通過(guò)head和walker一齊走，相遇點(diǎn)是cycle起點(diǎn)這層關(guān)系
Definitions:
Cycle = length of the cycle, if exists.
C is the beginning of Cycle, S is the distance of slow pointer from C when slow pointer meets fast pointer.
Distance(slow) = C + S, Distance(fast) = 2 * Distance(slow) = 2 * (C + S). To let slow poiner meets fast pointer, only if fast pointer run 1 cycle more than slow pointer. Distance(fast) - Distance(slow) = Cycle
=> 2 * (C + S) - (C + S) = Cycle
=> C + S = Cycle
=> C = Cycle - S
=> This means if slow pointer runs (Cycle - S) more, it will reaches C. So at this time, if there's another point2(we use head Here) running from head
=> After C distance, point2 will meet slow pointer at C, where is the beginning of the cycle.
public ListNode detectCycle(ListNode head) {
ListNode walker = head;
ListNode runner = head;
//這里不加runner.next.next!=null也ac
while(runner!=null&&runner.next!=null&&runner.next.next!=null){
runner = runner.next.next;
walker = walker.next;
if(runner==walker){
while(head!=walker){
head = head.next;
walker = walker.next;
}
return walker;
}
}
return null;
}
- 判斷兩個(gè)單鏈表是否相交----時(shí)間復(fù)雜度為O(len1+len2)，因?yàn)橹恍枰粋€(gè)額外指針保存最后一個(gè)節(jié)點(diǎn)地址，空間復(fù)雜度為O(1)。
如果兩個(gè)鏈表相交于某一節(jié)點(diǎn)，那么在這個(gè)相交節(jié)點(diǎn)之后的所有節(jié)點(diǎn)都是兩個(gè)鏈表所共有的。也就是說(shuō)，如果兩個(gè)鏈表相交，那么最后一個(gè)節(jié)點(diǎn)肯定是共有的。先遍歷第一個(gè)鏈表，記住最后一個(gè)節(jié)點(diǎn)，然后遍歷第二個(gè)鏈表，到最后一個(gè)節(jié)點(diǎn)時(shí)和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)做比較，如果相同，則相交，否則不相交。
public static boolean isIntersect(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return false;
}
Node tail1 = head1;
// 找到鏈表1的最后一個(gè)節(jié)點(diǎn)
while (tail1.next != null) {
tail1 = tail1.next;
}
Node tail2 = head2;
// 找到鏈表2的最后一個(gè)節(jié)點(diǎn)
while (tail2.next != null) {
tail2 = tail2.next;
}
return tail1 == tail2;
}
- 求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)----時(shí)間復(fù)雜度，O(len1+len2)
對(duì)第一個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len1，同時(shí)保存最后一個(gè)節(jié)點(diǎn)的地址。
對(duì)第二個(gè)鏈表遍歷，計(jì)算長(zhǎng)度len2，同時(shí)檢查最后一個(gè)節(jié)點(diǎn)是否和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)相同，若不相同，不相交，結(jié)束。
兩個(gè)鏈表均從頭節(jié)點(diǎn)開(kāi)始，假設(shè)len1大于len2，那么將第一個(gè)鏈表先遍歷len1-len2個(gè)節(jié)點(diǎn)，此時(shí)兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)到第一個(gè)相交節(jié)點(diǎn)的距離就相等了，然后一起向后遍歷，知道兩個(gè)節(jié)點(diǎn)的地址相同。
*
* ---- len2
* |__________
* |
* --------- len1
* |---|<- len1-len2
*/
public static Node getFirstCommonNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
int len1 = 1;
Node tail1 = head1;
while (tail1.next != null) {
tail1 = tail1.next;
len1++;
}
int len2 = 1;
Node tail2 = head2;
while (tail2.next != null) {
tail2 = tail2.next;
len2++;
}
// 不相交直接返回NULL
if (tail1 != tail2) {
return null;
}
Node n1 = head1;
Node n2 = head2;
// 略過(guò)較長(zhǎng)鏈表多余的部分
if (len1 > len2) {
int k = len1 - len2;
while (k != 0) {
n1 = n1.next;
k--;
}
} else {
int k = len2 - len1;
while (k != 0) {
n2 = n2.next;
k--;
}
}
// 一起向后遍歷，直到找到交點(diǎn)
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
160. Intersection of Two Linked Lists
- 一個(gè)general的方法, 比較兩個(gè)linked list的長(zhǎng)度，把較長(zhǎng)的一個(gè)鏈表后移幾位，從長(zhǎng)度和另一鏈表相等處開(kāi)始比較node是否相同。
一開(kāi)始在想相交之后還會(huì)不會(huì)分開(kāi)，比如一開(kāi)始就相交，那長(zhǎng)度不等情況下先向后移就說(shuō)不過(guò)去了，但是這里應(yīng)該是利用了鏈表特性，每個(gè)node都指向另一個(gè)node，所以相交之后就一定都一樣了。 - 一個(gè)很機(jī)智的方法，感覺(jué)用到了類(lèi)似single linked list中判斷是否有cycle時(shí)候用的runner 和walker雙指針的方法，這個(gè)題中的“雙指針”總會(huì)在intersection處相遇或者沒(méi)有intersection在最后的null相遇.
disscuss區(qū)大神的分析: - use two iterations here. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference.
So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null - The problem description especially required the code to run in O(n) time and O(1) space. Thus I came up with the most direct way.
Just count the lengths of both lists, set two pointers from the list heads, align them to equipotential position and move'em forward until they coincide.
That would be the answer we seek.
Time complexity should be O(n + m), if you name the lengths of both lists to be "n" and "m". Extra space required is O(1). - Notice：只貼一下第二個(gè)方法，第一個(gè)方法很簡(jiǎn)單，分別遍歷鏈表直到空，通過(guò)counter獲取長(zhǎng)度，然后通過(guò)兩個(gè)長(zhǎng)度差值移動(dòng)指向較長(zhǎng)鏈表的node的位置，在等長(zhǎng)之后比較node是否相同，是就返回該node。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while( a != b){
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
- 已知一個(gè)單鏈表中存在環(huán)，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)
上面貼的leetcode142
首先判斷是否存在環(huán)，若不存在結(jié)束。在環(huán)中的一個(gè)節(jié)點(diǎn)處斷開(kāi)（當(dāng)然函數(shù)結(jié)束時(shí)不能破壞原鏈表），這樣就形成了兩個(gè)相交的單鏈表，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)也就轉(zhuǎn)換成了求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)。參考代碼如下：
/**
* 求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn) 用快慢指針做（本題用了Crack the Coding Interview的解法，因?yàn)楦?jiǎn)潔易懂?。? */
public static Node getFirstNodeInCycle(Node head) {
Node slow = head;
Node fast = head;
// 1） 找到快慢指針相遇點(diǎn)
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // Collision
break;
}
}
// 錯(cuò)誤檢查，這是沒(méi)有環(huán)的情況
if (fast == null || fast.next == null) {
return null;
}
// 2）現(xiàn)在，相遇點(diǎn)離環(huán)的開(kāi)始處的距離等于鏈表頭到環(huán)開(kāi)始處的距離，
// 這樣，我們把慢指針?lè)旁阪湵眍^，快指針保持在相遇點(diǎn)，然后
// 同速度前進(jìn)，再次相遇點(diǎn)就是環(huán)的開(kāi)始處！
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 再次相遇點(diǎn)就是環(huán)的開(kāi)始處
return fast;
}
- 給出一單鏈表頭指針pHead和一節(jié)點(diǎn)指針pToBeDeleted，O(1)時(shí)間復(fù)雜度刪除節(jié)點(diǎn)pToBeDeleted----總體的平均時(shí)間復(fù)雜度還是O(1)
對(duì)于刪除節(jié)點(diǎn)，我們普通的思路就是讓該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，這種情況需要遍歷找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)。對(duì)于鏈表，鏈表中的每個(gè)節(jié)點(diǎn)結(jié)構(gòu)都是一樣的，所以我們可以把該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到該節(jié)點(diǎn)，然后刪除下一個(gè)節(jié)點(diǎn)即可。要注意最后一個(gè)節(jié)點(diǎn)的情況，這個(gè)時(shí)候只能用常見(jiàn)的方法來(lái)操作，先找到前一個(gè)節(jié)點(diǎn)，但總體的平均時(shí)間復(fù)雜度還是O(1)。參考代碼如下：
public void delete(Node head, Node toDelete){
if(toDelete == null){
return;
}
if(toDelete.next != null){ // 要?jiǎng)h除的是一個(gè)中間節(jié)點(diǎn)
toDelete.val = toDelete.next.val; // 將下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到本節(jié)點(diǎn)!
toDelete.next = toDelete.next.next;
}
else{ // 要?jiǎng)h除的是最后一個(gè)節(jié)點(diǎn)！
if(head == toDelete){ // 鏈表中只有一個(gè)節(jié)點(diǎn)的情況
head = null;
}else{
Node node = head;
while(node.next != toDelete){ // 找到倒數(shù)第二個(gè)節(jié)點(diǎn)
node = node.next;
}
node.next = null;
}
}
}
規(guī)律總結(jié)
- DummyNode
做鏈表題目時(shí)，如果head可能被改變，我們需要?jiǎng)?chuàng)建一個(gè)虛擬節(jié)點(diǎn)，叫DummyNode，把頭部掛在它的后面。這樣就算頭部變化了之后，只要返回DummyNode.next就能輕松得到新頭部。 - Merge LinkedList是相當(dāng)基礎(chǔ)的題目，merge的半成品代碼上面也有提到。
- Reverse linkedList最簡(jiǎn)單的寫(xiě)法就是創(chuàng)建DummyNode，然后把舊的鏈表不斷插入到DummyNode的后面，就能輕松地返回鏈表了。
- 操作鏈表的時(shí)候，我們經(jīng)常會(huì)改變某些Node。如果后面還需要再用到被改變掉節(jié)點(diǎn)的原始值，請(qǐng)一定記得用tmp先把它保存起來(lái)。
