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

單鏈表的反轉(zhuǎn)

頭插法
兩個指針，next 表示 head 的后一個節(jié)點(diǎn)，pre 表示 head 的前一個節(jié)點(diǎn)，都作為臨時節(jié)點(diǎn)
先把 head 節(jié)點(diǎn)指向后面節(jié)點(diǎn)的指針保存起來 next = head.next ，則此時 next 節(jié)點(diǎn)和 2 節(jié)點(diǎn)值和指針是相同的
head 指向前一個節(jié)點(diǎn) head.next = pre
pre 與 head 進(jìn)行右移 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;
}

鏈表的倒數(shù)第 K 個節(jié)點(diǎn)

1.雙指針解決
2.fast 先走K步，然后 low 開始走，fast 走到結(jié)尾的時候 low 則指向倒數(shù)第 K 個節(jié)點(diǎn)
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;
}

鏈表是否有環(huán)、環(huán)的入口

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

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){
            // 相遇時 終止循環(huán)
            break;
        }
    }
    if (fast != slow){
        return null;
    }
    fast = head;  // 將其中一個指針指向開頭
    while (fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    // 再次相遇時即為環(huán)入口點(diǎn)
    return fast;
}

歡迎加入學(xué)習(xí)交流群569772982，大家一起學(xué)習(xí)交流。