?1.反轉鏈表

題目：

解題思路：
如下圖，我們要實作的就是這樣一個效果

要實作上圖的效果，需要以下步驟：
①設定兩個指標，cur 指向鏈表頭節點，prev 指向空
②暫存 cur 的后繼節點，curNext = cur.next
③將 cur.next 反指向prev（一開始prev為空）
④prev 指標后移，即將 prev 指向 cur
⑤cur 指標后移 ，即將 cur 指向 2 中暫存的 curNext 節點
⑥回圈： 第2 到 5 步，直到 cur 遍歷完整個鏈表

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode reverseList(ListNode head) {
       if(head==null){
           System.out.println("鏈表為空");
       }
      //設定兩個指標，cur 指向鏈表頭節點，prev 指向空
       ListNode prev = null;
       ListNode cur = head;

       while(cur != null){
           ListNode curNext = cur.next;//暫存 cur 的后繼節點，curNext = cur.next
           cur.next =prev;//將 cur.next 反指向prev（一開始prev為空）
           prev = cur;//prev 指標后移，即將 prev 指向 cur
           cur = curNext;//cur 指標后移 ，即將 cur 指向 2 中暫存的 curNext 節點
       }//回圈： 第2 到 5 步，直到 cur 遍歷完整個鏈表
       return prev;
   }
}

?2.給定一個帶有頭結點 head 的非空單鏈表，回傳鏈表的中間結點

題目：

解題思路：
本題用的是雙指標的方法
①分別設定一個快指標和一個慢指標
②快指標每次走兩步，慢指標每次走一步
③當快指標走到最后尾節點的時候，慢指標就走到了鏈表中間節點

/**
* Definition for singly-linked list.
* 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) {
       ListNode fast = head;//快指標一開始指向頭結點
       ListNode slow = head;//慢指標一開始也指向頭結點
       while(fast!=null&&fast.next!=null){//由于要考慮偶數鏈表回傳中間靠后的節點
       //所以要多設定一個fast.next!=null條件
           fast=fast.next.next;//快指標往后走兩步
           slow=slow.next;//慢指標往后走一步
       }
       return slow;//回傳慢指標
   }
}

?3.輸入一個鏈表輸出該鏈表中倒數第K個節點

題目：

解題思路：
這題和上題一樣，采用雙指標的辦法，遍歷鏈表一次就能達到目的

具體需要以下步驟：
①初始化： 前指標 former 、后指標 latter ，雙指標都指向頭節點 head? ，
②構建雙指標距離： 前指標 former 先向前走 k-1 步（結束后，雙指標 former 和 latter 間相距 k-1步），
③雙指標共同移動： 回圈中，雙指標 former 和 latter 每輪都向前走一步，直至 former 走到鏈表 尾節點 時跳出（跳出后， latter 與尾節點距離為 k-1步，即 latter 指向倒數第 k 個節點）
④回傳值： 回傳 latter 即可，

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode getKthFromEnd(ListNode head, int k) {
       ListNode former = head;//設定一個先行節點，一開始指向頭結點
       ListNode latter = head;//再設定一個后行節點，一開始指向頭結點
       for(int i=1; i < k; i++){//構建雙節點之間距離
           former = former.next;//
      }
       //構建距離完成之后，雙節點同時向后走，直至先行節點到達尾節點處
       while(former.next!=null){//
           former = former.next;//
           latter = latter.next;//
       }
       return latter;//此時latter距離尾節點k-1步，也就是指向倒數第k個節點，直接回傳latter即可
   }
}

?4.將兩個有序鏈表合并為一個新的有序鏈表并回傳

題目：

解題思路：

具體步驟如下
①設定傀儡節點，傀儡節點后邊的節點組成的鏈表就是合并后的鏈表
②比較兩個鏈表的每個節點，存入傀儡節點后的合并鏈表
③當有一條鏈已經遍歷完成則將另一條鏈接到合并鏈表的尾部
④最后回傳的是傀儡節點的下一個節點，這才是合并后的鏈表的頭結點

/**
* Definition for singly-linked list.
* 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(-1);//創建一個虛擬傀儡節點，最后回傳的是.next
       ListNode tmp =newhead;//創建區域參考，指向傀儡節點
       while (l1!=null && l2!=null) {//依次比較節點
           if (l1.val < l2.val) {//情況1
               tmp.next = l1;//將節點存入合并鏈表
               l1 = l1.next;//L2往后走一步
               tmp = tmp.next;//合并鏈表也要往后走一步好用于儲存下一個比較結果
           } else {             //情況2
               tmp.next = l2;//將節點存入合并鏈表
               l2 = l2.next;//L2往后走一步
               tmp = tmp.next;//合并鏈表也要往后走一步好用于儲存下一個比較結果
           }
       }
       if (l1==null){//當第一條鏈先走完
           tmp.next = l2;//將第二條鏈接到合并鏈表后
       }
       if (l2==null){//當第二條鏈先走完
           tmp.next = l1;//將第一條鏈接到合并鏈表后
       }
       return newhead.next;//最侄訓傳傀儡節點的下一個節點，也就是合并鏈表的頭結點
}

?5.分割鏈表

題目：

解題思路：
①本題用的雙鏈表的方法，分別寫一個A鏈表和B鏈表，A鏈表放值小于X的節點，B鏈表放值大于X的節點，依次遍歷原鏈表就行了
②不過要注意一個關鍵點，遍歷結束后，我們將 L2 的next指標置空，這是因為當前節點復用的是原鏈表的節點，而其 指標可能指向一個小于 xx 的節點，我們需要切斷這個參考
③最后將兩個鏈表合成一個鏈表即可 （L1.next指向B.next就可以了）

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode partition(ListNode head, int x) {
       ListNode headA=new ListNode();//設定一個傀儡節點A，代表A鏈表
       ListNode headB=new ListNode();//再設定一個傀儡節點B，代表B表
       ListNode l1 = headA;//區域參考l1
       ListNode l2 = headB;//區域參考l2
       ListNode cur= head;//區域參考cur
       while(cur!=null){//遍歷原鏈表
           if(cur.val<x){//小于X放A
               l1.next=cur;
               l1=l1.next;
           }else{        //大于X放B
               l2.next=cur;
               l2=l2.next;
           }
           cur=cur.next;//依次遍歷
       }
       l2.next=null;//遍歷結束后，我們將 l2 的next指標置空
       //這是因為當前節點復用的是原鏈表的節點，而其指標可能指向一個小于 xx 的節點
       //我們需要切斷這個參考
       l1.next=headB.next;//鏈接兩個鏈表，A的尾巴指向B的頭
       return headA.next;//回傳A的next，因為第一個節點其實是傀儡節點
       //第二個開始才是A鏈表的頭結點
   }
}

?6.洗掉鏈表中重復節點（重復節點不保留）

題目：

解題思路：
主要思想就是遍歷原鏈表，將不重復的節點提取出來放到一個新的鏈表里
①遍歷原鏈表（利用臨時變數cur代替頭結點）
②創建一個新頭結點，代表一個新鏈表
③判斷當前節點與下一個節點是否相同，如果相同則cur往后走一步，不同則將此節點存入新節點
④回傳新頭結點的下一節點（新頭結點其實是傀儡節點，新鏈表其實是從第二個節點開始的）

public ListNode deleteDuplicates(ListNode head) {
       ListNode cur = head;//設定臨時變數代替頭結點遍歷原鏈表
       ListNode newHead = new ListNode(-1);//創建一個新頭結點代表一個新的鏈表
       ListNode tmp = newHead;//設定臨時變數代替新鏈表的頭結點
       while (cur != null) {//設定終止條件
           if (cur.next != null && cur.val == cur.next.val) {
           //判斷當前節點值是否等于下一個節點
           //前提是下一個節點不為null，不然會有空指標導致訪問例外
               while (cur.next != null && cur.val == cur.next.val) {
               //這里還需要考慮到有兩個以上重復的節點怎么處理
               //所以還需要一個while來跳過重復節點
                   cur = cur.next;
               }
               cur = cur.next;//往后多走一步，因為題目要求不需要保留重復節點
           } else {//不滿足等值條件的點，直接跳過，往后遍歷即可
               tmp.next = cur;
               tmp = tmp.next;
               cur = cur.next;
         }
       }
       //防止最后一個節點值也是重復的
       tmp.next = null;//因為cur是原鏈表的參考，后邊還會指向原鏈表中的節點
       //所以要置空，只保留當時cur指向的那個節點
       return newHead.next;
   }

?7.判斷鏈表是否是回文結構

題目：

解題思路：
本題首先得了解什么是回文結構，回文結構就是正著讀反著讀都一樣的鏈表
①快慢指標法找中間節點
②后半段鏈表反轉
③判斷兩端鏈表是否相同
④注意考慮鏈表為偶數的情況

public boolean isPalindrome(ListNode head) {
       ListNode fast = head;
       ListNode latter = head;

       //找中間點
       while(fast!=null&&fast.next!=null){//經典的快慢指標法找中間點，就不多bb了
           fast=fast.next.next;
           latter=latter.next;
       }
       //后半段反轉
       ListNode cur=latter.next;
       while(cur!=null){//經典的反轉鏈表，也不多BB了，具體方法請看第一題
           ListNode curNext=cur.next;//設定暫存點
           cur.next=latter;
           latter=cur;
           cur = curNext;
       }

       //判斷兩段鏈表是否相同
       while(head!=latter){//head從頭往后走，latter從后往前走，直到相遇
           if(head.val==latter.val){//判斷兩段鏈表值是否相等
              if (head.next == latter) {//考慮鏈表為偶數的情況
                    return true;//偶數鏈表的情況頭結點下一個節點就是latter的時候直接回傳true
               }
           }
           else{
               return false;
           }
           latter=latter.next;//latter依次遍歷
           head=head.next;//head依次遍歷
       }
       return true;//能跳出回圈說明，鏈表符合回文結構，回傳true
   }

?8.找出兩個鏈表的第一個公共節點

題目：

解題思路：這里說一種很6P的解法，是leetcode上看到的一個題解
直接將兩條路分別拼接在對方末尾，這樣兩條路便一樣長，再從這兩條新的路起始點往后比較即可，如下圖 節點相同地方一句圈起來，兩條鏈表記住，公共節點指的就是公用一個節點，不是值相同，所以要對比的是地址，藍色連接代表鏈表結束換路
①設定兩個臨時節點節點，分別指向A鏈表頭結點和B鏈表頭結點
②只要這兩個臨時節點不指向同一個地址，就說明還沒走到第一個公共節點
③當臨時節點走到一條鏈表的尾節點時（p1/p2.nextnull）就走另外一條鏈
④啥時候p1等于p2了，即p1和p2指向同一個地址了==，這個地址就是第一個公共節點的地址，回傳其即可

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode p1 = headA, p2 = headB;//設定兩個臨時節點節點
                                       //分別指向A鏈表頭結點和B鏈表頭結點
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;//p1依次往后遍歷，走到尾節點了就走另一條鏈表
            p2 = p2 == null ? headA : p2.next;//p2依次往后遍歷，走到尾節點了就走另一條鏈表
        }
        return p1;//跳出回圈了說明找到公共節點了
   }

?9.判斷鏈表是否有環

題目：

解題思路：
找環其實就是一個追擊問題，依舊采取雙指標的方法，設定一個快指標一個慢指標，快指標每次走兩步，慢指標每次走一步，如果鏈表有環，快指標和慢指標終究會相遇，因為跑的快的人最終肯定會超跑得慢的人一圈，當他們相遇的時候剛好超了一圈
①設定一個快指標，一個慢指標
②兩個指標都指向頭結點
③快指標每次走兩步，慢指標每次走一步
④如果有環，兩個指標一定會在某一時刻相遇，否則無環

public boolean hasCycle(ListNode head) {
       ListNode fast = head;//設定快指標，指向頭結點
       ListNode slow = head;//設定慢指標，指向頭結點
       ListNode cur = head;//設定臨時變數代替頭結點，用于遍歷鏈表

       while(fast!=null&&fast.next!=null ){
           fast=fast.next.next;//快指標每次走兩步
           slow=slow.next;//慢指標每次走一步
           if(fast==slow)//快慢指標相遇
           return true;//說明有環
       }
       return false;//快慢指標沒相遇說明無環
   }

?10.回傳鏈表開始入環的第一個節點

題目：

解題思路：
我們使用兩個指標，fast 與 slow，它們起始都位于鏈表的頭部，隨后，slow 指標每次向后移動一個位置，而fast 指標向后移動兩個位置，如果鏈表中存在環，則 fast 指標最終將再次與 slow 指標在環中相遇
如下圖所示，設鏈表中環外部分的長度為 a，slow 指標進入環后，又走了 b 的距離與 fast 相遇，此時，fast 指標已經走完了環的 n 圈，因此它走過的總距離為 a+n(b+c)+b=a+(n+1)b+nc
根據題意，任意時刻，fast 指標走過的距離都為slow 指標的 2 倍，因此，我們有
a+(n+1)b+nc=2(a+b)?a=c+(n?1)(b+c)
有了 a=c+(n-1)(b+c)的等量關系，我們會發現：從相遇點到入環點的距離加上 n-1圈的環長，恰好等于從鏈表頭部到入環點的距離，
因此，當發現 slow 與 fast 相遇時，我們再額外使用一個指標 tmp它指向鏈表頭部；隨后，它和 slow 每次向后移動一個位置，最終，它們會在入環點相遇，
解題步驟：
①利用快慢指標方法找相遇點
②找到相遇點之后，設定臨時變數tmp代替頭結點，tmp和slow同時移動，直至相遇
③相遇點即為環的呃入口

public ListNode detectCycle(ListNode head) {
           if(head==null||head.next==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){
               break;
           }
       }
       //找到相遇點后，用臨時變數代替頭結點
       if (fast==slow){
           ListNode tmp = head;//臨時變數代替頭結點
           while(tmp!=slow){//tmp和slow同時移動
               slow = slow.next;
               tmp = tmp.next;
           }
           return tmp;//tmp和slow相遇的節點就是環的入口點
       }
       return null;
   }

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙