文章目錄
- 一、洗掉鏈表中等于給定值 **val** 的所有節點
- 二、反轉單鏈表
- 三、找鏈表的中間結點
- 四、找鏈表中的第k個結點
- 五、合并兩個有序鏈表
- 六、分隔鏈表
- 七、洗掉排序鏈表中的重復元素
- 八、判斷一個鏈表是否是回文鏈表
- 九、兩個鏈表的第一個公共節點
- 十、判斷一個鏈表是否有環
- 十一、判斷一個鏈表是否有環，并回傳第一個結點
一、洗掉鏈表中等于給定值 val 的所有節點
對應leetcode題
因為要洗掉某一個結點，就要遍歷到該結點之前的位置，為了記錄需要洗掉的結點的前一位置，我們需要另外創建一個指標pre來記錄，先不對頭結點進行判斷它的val值是否等于val，因此只需將cur設為頭結點的后一個結點即可，若先對頭指標判斷，則可能需要不斷地改變頭指標，會非常麻煩，因此先遍歷整個鏈表，如果遇到有需要洗掉的結點，則有pre.next=cur.next；cur=cur.next；否則pre=cur;cur=cur.next;
如果23為需要洗掉的結點，則有以下的例子：
圖解：
遇到需要洗掉的結點：pre.next=cur.next；cur=cur.next
遇到不需要洗掉的結點：當cur為空時，則退出回圈，遍歷結束后還要判斷頭結點的 值是否等于val，
代碼示例：
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null) {
return null;
}
ListNode cur = head.next;
ListNode pre = head;
while(cur!=null) {
if(cur.val==val) {
pre.next=cur.next;
cur=cur.next;
} else {
pre=cur;
cur=cur.next;
}
}
if(head.val==val) {
head=head.next;
}
return head;
}
}
二、反轉單鏈表
對應leetcode題
對應如圖所示：
為了反轉鏈表，我們需要設定三個參考，因為一個要記錄前面的位置pre，一個要記錄后面的位置curNext，還有一個要作為鏈接鏈表的點cur，因為頭結點會隨著反轉鏈表的改變而改變，因此要設定一個新的頭結點newHead，
代碼示例：
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode curNext = null;
ListNode newHead = null;
while(cur!=null) {
curNext=cur.next;
if(curNext==null) {
newHead=cur;
}
cur.next=pre;
pre=cur;
cur=curNext;
}
return newHead;
}
}
三、找鏈表的中間結點
對應leetcode題
尋找中間結點，我們要找到路程與速度的規律，速度兩倍的路程也是兩倍，因此說明我們可以設定兩個指標來走，如果一個指標是另一個指標速度的兩倍，當它走到鏈表尾時，則另一個指標在鏈表的中間，因此走的慢的那個指標的位置就是中間結點的位置，但是有兩種情況：第一種是單鏈表的結點數為奇數，第二種是單鏈表的結點數為偶數，
因此有兩種情況：結點數為偶數時判斷fast.next是否為null，結點數為奇數時判斷fast是否為null，當兩種情況下只有一種情況滿足，則直接回傳slow指標即可找到中間結點，
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
四、找鏈表中的第k個結點
對應leetcode題
我們用雙指標來解這道題，我們發現，如果倒數第三個結點走到最后一個結點需要2步，如果倒數第二個結點走到最后一個結點需要1步，因此有這樣的規律：從第k個結點開始走到最后一個結點需要走k-1步，我們假設頭結點就是“最后一個結點”，因此讓一個fast指標走k-1步，此時是鏈表倒置的第k個結點，而此時兩個指標同時走，當發現fast指標走到fast.next值為null時，則找到第k個結點，第k個結點的位置就是slow指標所指向的位置，slow與fast一開始指向head，
圖解：
fast走k-1步：
fast與slow同時走，判斷條件為fast.next不為null
代碼示例：
public ListNode getKthFromEnd(ListNode head, int k) {
if(head==null) {
return null;
}
if(k<0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k-1!=0) {
fast=fast.next;
if(fast==null) {
return null;
}
k--;
}
while(fast!=null&&fast.next!=null) {
fast=fast.next;
slow=slow.next;
}
return slow;
}
五、合并兩個有序鏈表
對應leetcode題
此處我們設定一個新的頭結點，將兩個單鏈表串起來，因為是按照升序來連接鏈表，因此每次都需要判斷l1的值與l2的值誰大誰小，小的先連接，而為了新的頭結點不改變，需要另一個指標從頭結點開始對l1或者l2連接，因為l1與l2的長度可能不同，因此有可能會先連完一條鏈，而另一條鏈直接連在新的鏈表當中即可，
圖解：準備作業：
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newHead = new ListNode();
ListNode tmp = newHead;
if(l1==null&&l2==null) {
return null;
}
if(l1==null) {
newHead.next=l2;
}
if(l2==null) {
newHead.next=l1;
}
while(l1!=null&&l2!=null) {
if(l1.val>l2.val) {
tmp.next=l2;
l2=l2.next;
tmp=tmp.next;
} else {
tmp.next=l1;
l1=l1.next;
tmp=tmp.next;
}
}
if(l1==null) {
tmp.next=l2;
}
if(l2==null) {
tmp.next=l1;
}
return newHead.next;
}
}
六、分隔鏈表
對應leetcode題
為了分開鏈表中小于val值得結點，我們設定兩個新的鏈表，用空間來換取時間，因此兩個新的鏈表有頭結點與臨時結點，一邊放入小于val值的結點，另一邊放入大于和等于val值的結點，但放入結點時有兩種情況，第一種情況時第一次放入時，兩個新的鏈表都無指向，因此第一次應該直接指向原來的鏈表中即可，除了第一次為特殊情況外，新的鏈表的指標指向的都是原來的鏈表中cur遍歷所指向的該結點，而臨時指標也需要向后移一位，而cur也需要后移一位，
需要注意的是：
- 如果bs為null則需要改變be的next值為null，否則還會指向某一個結點，
- 如果as為null則直接回傳bs即可，
- 最后將兩個新的鏈表合起來，則需要有
ae.next=bs;
圖解：
代碼示例：
public ListNode partition(ListNode head, int x) {
ListNode as = null;
ListNode ae = null;
ListNode bs = null;
ListNode be = null;
ListNode tmp = head;
while(tmp!=null) {
if(tmp.val<x) {
if(as==null) {
as=tmp;
ae=tmp;
} else {
ae.next=tmp;
ae=ae.next;
}
} else {
if(bs==null) {
bs=tmp;
be=tmp;
} else {
be.next=tmp;
be=be.next;
}
}
tmp=tmp.next;
}
if(as==null) {
return bs;
}
ae.next=bs;
if(bs!=null) {
be.next=null;
}
return as;
}
七、洗掉排序鏈表中的重復元素
對應leetcode題
因為一個鏈表中重復的元素有多個，并且要求全部洗掉，則我們需要一個回圈來遍歷鏈表并且創建指標cur從頭結點開始，判斷cur.val==cur.next.val，如果相等則跳過重復的元素，當然此時要注意要判斷cur.next一定不能為null，否則cur.next.val會空指標例外，示例如下：
但是tmp需要連接的是第三個結點，因此cur此時還要向后移一位，才有tmp.next=cur;cur=cur.next;tmp=tmp.next但是cur.next已經為null了，因此要退出回圈，再將tmp.next=null ，
代碼示例：
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode newHead = new ListNode(-1);
ListNode cur = head;
ListNode tmp = newHead;
while(cur!=null) {
if(cur.next!=null&&cur.val==cur.next.val) {
while(cur.next!=null&&cur.val==cur.next.val) {
cur=cur.next;
}
cur=cur.next;
} else {
tmp.next=cur;
cur=cur.next;
tmp=tmp.next;
}
}
tmp.next=null;
return newHead.next;
}
}
八、判斷一個鏈表是否是回文鏈表
對應leetcode題
回文鏈表指的是鏈表兩邊的結點的值對稱，如果為奇數不用判斷中間部分，我們第一步首先創建兩個指標slow和fast，讓slow走到中間結點的位置，就等同于找中間結點，第二步逆置slow后半部分的鏈表，就等同于逆置鏈表，思想上是一樣的，第三步是從head結點和slow結點處遍歷前半部分與后半部分鏈表，如果對應結點有不相同的val值，則回傳true，
圖解：
注意
1.slow走到中間時創建cur指標與curNext指標對鏈表進行逆置，當slow到達最后一個結點的條件為cur!=null，
2.判斷是否是回文鏈表，則情況有兩種，第一種是結點數量為奇數時有head!=slow，第二種是結點數量為偶數時有head.next!=slow，
結點數為偶數時需要判斷：如果能夠走到head與slow相遇則回傳true，否則回傳false，
結點數為偶數時需要判斷head.next==slow，否則在鏈表中如果head與slow“擦肩而過”等同于不相遇，
代碼示例：
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode A) {
if(A==null) {
return true ;
}
ListNode fast = A;
ListNode slow = A;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow = slow.next;
}
ListNode cur = slow.next;
while(cur!=null) {
ListNode curNext = cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
while(A.val==slow.val) {
if(A.next==slow||A==slow) {
return true;
}
A=A.next;
slow=slow.next;
}
return false;
}
}
九、兩個鏈表的第一個公共節點
對應leetcode題
找兩個鏈表的公共結點，首先想到的是先設定兩個指標從兩個鏈表的頭開始，讓相對長的鏈表先走兩個鏈表的長度差值，再讓兩個指標一起走，相遇的點就是它們的公共點，我們假設p1指向的始終是較長的鏈表，p2指向的是較短的鏈表，因此可以分為三步：第一步求出兩個鏈表的長度的差值；第二步讓鏈表走長度差值步，第三步讓兩個指標一起走，判斷的終點為兩個指標相遇，
圖解：
代碼示例1：這種相對來說好理解一些，
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0 ;
int lenB = 0 ;
while(pl!=null) {
pl=pl.next;
lenA++;
}
pl=headA;
while(ps!=null) {
ps=ps.next;
lenB++;
}
ps=headB;
int len = lenA-lenB;
if(len<0) {
pl=headB;
ps=headA;
len = lenB-lenA;
}
while(len!=0) {
pl=pl.next;
len--;
}
while(pl!=ps) {
pl=pl.next;
ps=ps.next;
}
return pl;
}
代碼示例2：這種代碼可讀性不太強，但是更加簡潔，原理相同，
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
十、判斷一個鏈表是否有環
對應leetcode題
設定兩個指標fast和slow，都從頭結點處開始走，fast指標一次走兩步，slow指標一次走一步，如果最后相遇，則該鏈表肯定有環，如果fast指標為null，則該鏈表不是環形鏈表，
圖解：
代碼示例：
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow) {
return true;
}
}
return false;
}
}
十一、判斷一個鏈表是否有環，并回傳第一個結點
對應leetcode題
給定一個鏈表，回傳鏈表開始入環的第一個節點， 如果鏈表無環，則回傳 null，
如果該鏈表是一個環形鏈表，則它的形狀如下圖所示，我們設直線的起始位置為起始點，長度為a，而在走過長度b后在該小圓點處相遇，而長度c等于一個環的周長減去b，因此我們仍然可以設定雙指標fast和slow，fast指標一次走兩步，slow指標一次走一步，因此slow與fast指標在環中相遇時，fast有可能走了n圈環，而slow最多只可能走了一圈，而fast走的路程又是slow走的路程的兩倍，因此有以下公式：fast走的路程=a+n(b+c)+b，而slow走的路程=2(a+b)，因此有a+n(b+c)+b=2(a+b)，化簡得a=c+(n?1)(b+c)，因此，當發現 slow 與 fast 相遇時，我們再額外使用一個指標 ptr，起始，它指向鏈表頭部；隨后，它和 slow 每次向后移動一個位置，最終，它們會在入環點相遇，（slow可能走很多圈，但是從相遇處開始一步一步走一定會相遇，相遇時回傳slow或pte指標即可），
圖解：
代碼示例：
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow) {
ListNode pre = head;
while(pre!=slow) {
pre=pre.next;
slow=slow.next;
}
return pre;
}
}
return null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353395.html
標籤：其他
上一篇：劍指offer-之-哈希表
下一篇：搞懂緩沖區，看這篇文章就夠了