//leetcode中還有花樣鏈表題娱局，這里幾個(gè)例子闷袒，冰山一角
- 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)----時(shí)間復(fù)雜度O（n）
這是最最基本的了湿硝，應(yīng)該能夠迅速寫出正確的代碼，注意檢查鏈表是否為空贝乎。參考代碼如下：
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)朽肥，無需反轉(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
沒做過一上來感覺不太好想每强，有個(gè)視頻，看到一半恍然大悟：https://www.youtube.com/watch?v=sYcOK51hl-A
這類題都開始要求用iteration寫一次再用recursive寫一個(gè)
//假設(shè)1->2->3->4,先從head=1開始州刽，要翻轉(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)開始
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í)這三種情況情況。代碼不寫了锦茁。
- 另一個(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)用于上一題類似的思想。也是設(shè)置兩個(gè)指針挠铲，只不過這里是冕屯，兩個(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ì)于這種顛倒順序的問題念颈，我們應(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è)類似歸并排序。尤其注意兩個(gè)鏈表都為空，和其中一個(gè)為空時(shí)的情況躏嚎。
21. Merge Two Sorted Lists
還是iteration和recursion,iteration代碼太長了蜜自，由此可見遞歸的好處，代碼簡(jiǎn)介易懂
iteration注意 l1,l2挨個(gè)merge的時(shí)候?yàn)榱朔奖憬羲鳎琹1,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;
// 先確定下來mergeHead是在哪里
if (head1.val < head2.val) {
mergeHead = head1;
head1 = head1.next; // 跳過已經(jīng)合并了的元素荞彼，指向已merge的node的next
mergeHead.next = null; // 斷開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; // 跳過已經(jīng)合并了的元素
mergeCur = mergeCur.next; // 找到下一個(gè)準(zhǔn)備合并的元素
mergeCur.next = null; // 斷開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的特性鸣皂，我們可以通過重寫compare方法利用priority queue實(shí)現(xiàn)，還有dummy暮蹂，從后向前拼接寞缝。
和下面sort里179一樣，都重寫了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)被啼，也就是說用一個(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è)代碼貼出來了勘伺，因?yàn)榕卸l件那里需要注意，這道題的寫法是褂删，先判斷了head==null飞醉，之后while中判斷runner.next和runner.next.next，個(gè)人理解是runner跑的快，需要注意判斷runner而不是walker缅帘。下一題的寫法看起來跟這個(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è)問題上道題中解釋了
這個(gè)題目的思路不太好想逗栽，discuss中有一個(gè)很好的解釋，貼過來失暂，其中關(guān)鍵的兩點(diǎn)是彼宠，walker走過的距離和cycle長度的關(guān)系，以及walker,runner相遇之后再通過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è)鏈表所共有的。也就是說系宫，如果兩個(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ì)算長度len1屯碴，同時(shí)保存最后一個(gè)節(jié)點(diǎn)的地址描睦。
對(duì)第二個(gè)鏈表遍歷，計(jì)算長度len2导而，同時(shí)檢查最后一個(gè)節(jié)點(diǎn)是否和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)相同忱叭，若不相同，不相交今艺，結(jié)束韵丑。
兩個(gè)鏈表均從頭節(jié)點(diǎn)開始，假設(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;
// 略過較長鏈表多余的部分
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的長度，把較長的一個(gè)鏈表后移幾位碗短，從長度和另一鏈表相等處開始比較node是否相同受葛。
一開始在想相交之后還會(huì)不會(huì)分開，比如一開始就相交偎谁，那長度不等情況下先向后移就說不過去了总滩，但是這里應(yīng)該是利用了鏈表特性，每個(gè)node都指向另一個(gè)node搭盾，所以相交之后就一定都一樣了咳秉。 - 一個(gè)很機(jī)智的方法，感覺用到了類似single linked list中判斷是否有cycle時(shí)候用的runner 和walker雙指針的方法鸯隅，這個(gè)題中的“雙指針”總會(huì)在intersection處相遇或者沒有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)單，分別遍歷鏈表直到空蝌以，通過counter獲取長度炕舵，然后通過兩個(gè)長度差值移動(dòng)指向較長鏈表的node的位置，在等長之后比較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)處斷開（當(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ò)誤檢查硝训，這是沒有環(huán)的情況
if (fast == null || fast.next == null) {
return null;
}
// 2）現(xiàn)在，相遇點(diǎn)離環(huán)的開始處的距離等于鏈表頭到環(huán)開始處的距離新思，
// 這樣窖梁，我們把慢指針放在鏈表頭，快指針保持在相遇點(diǎn)夹囚，然后
// 同速度前進(jìn)纵刘，再次相遇點(diǎn)就是環(huán)的開始處！
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 再次相遇點(diǎn)就是環(huán)的開始處
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í)候只能用常見的方法來操作赊淑，先找到前一個(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)單的寫法就是創(chuàng)建DummyNode，然后把舊的鏈表不斷插入到DummyNode的后面牍汹，就能輕松地返回鏈表了铐维。
- 操作鏈表的時(shí)候，我們經(jīng)常會(huì)改變某些Node慎菲。如果后面還需要再用到被改變掉節(jié)點(diǎn)的原始值嫁蛇，請(qǐng)一定記得用tmp先把它保存起來。
