摘要：單鏈表的反轉頭插法兩個指針，表示的后一個節點，表示的前一個節點，都作為臨時節點先把節點指向后面節點的指針保存起來，則此時節點和節點值和指針是相同的指向前一個節點與進行右移，遞歸斜體文字鏈表的倒數第個節點雙指針解決先走步，然后開始走，走到結尾

單鏈表的反轉

頭插法
兩個指針，next 表示 head 的后一個節點，pre 表示 head 的前一個節點，都作為臨時節點
先把 head 節點指向后面節點的指針保存起來 next = head.next ，則此時 next 節點和 2 節點值和指針是相同的
head 指向前一個節點 head.next = pre
pre 與 head 進行右移 pre = head，head = next

public static ListNode ReverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    if (head == null || head.next == null){
        return head;
    }
    while (head != null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
遞歸
*斜體文字*public static ListNode ReverseListStack(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = ReverseListStack(head.next);
    head.next.next = head;
    head.next = null;
    return node;
}

鏈表的倒數第 K 個節點

1.雙指針解決
2.fast 先走K步，然后 low 開始走，fast 走到結尾的時候 low 則指向倒數第 K 個節點
3.主要 異常情況，K < 0 ，K > len(List)

public static ListNode getKNode(ListNode head,int k){
    if (head == null || k < 0){
        return null;
    }
    ListNode pre = head;
    ListNode next = head;
    for (int l = 0; l < k; l++) {
        if (next != null) {
            next = next.next;
        }else {
            return null;
        }
    }
    while (next != null){
        pre = pre.next;
        next = next.next;
    }
    return pre;
}

鏈表是否有環、環的入口

1.快慢指針，快指針每次走兩步，慢指針每次走一步
2.若在遍歷鏈表的過程中，出現 快指針指向的節點等于慢指針指向的節點，說明鏈表有環，并且相遇的點一定在環中（不然不可能相遇）
3.設定 鏈表頭到環入口的距離為 x ，環入口到相遇點的距離為 a，環的總長度為 c，環相遇點到入口的距離為 b，則 a+b = c
4.假設此時快慢指針在環內相遇，那么
慢指針走過的距離 Step（low） = x + m * c + a （m為慢指針走過的圈數） ①
快指針走過的距離 Step（fast） = x + n * c + a （n為快指針走過的圈數） ②
Step（fast） = 2 * Step（low）③
5.根據①②③，得到 x = c （n - 2 m - 1）+ b ，也就是說鏈表頭到環入口的距離 x 等于 環的長度 c 的倍數 + b
6.相遇時，此時若將慢（快）其中一個放到鏈表開頭，然后開頭的指針和環中的指針一起一步步走，那么開頭的指針走 x 步時，環中的指針將走 k 圈 + b 步，此時 兩指針再次相遇，并且相遇點位環入口點，即為所求

public static ListNode getCircleroot(ListNode head){
    if (head == null || head.next == null){
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast){
            // 相遇時 終止循環
            break;
        }
    }
    if (fast != slow){
        return null;
    }
    fast = head;  // 將其中一個指針指向開頭
    while (fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    // 再次相遇時即為環入口點
    return fast;
}

歡迎加入學習交流群569772982，大家一起學習交流。