Leetcode日記：92&206.反轉(zhuǎn)鏈表

92.反轉(zhuǎn)鏈表其中一段

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

92-題目分析

也不知道Leetcode是怎么排布的題的順序，但是唯一的可能是按題出現(xiàn)的頻率冀泻，因為這個92題是II常侣，206才是I。所以我們主要分析這道題弹渔。無非就是給你兩個數(shù)胳施，讓你翻轉(zhuǎn)第 M 個到底 N 個鏈表上的元素。

反轉(zhuǎn)問題確實也是鏈表中常見的一種類型肢专。而且這種題看似簡單舞肆，但思考起來很容易搞亂。下面從代碼的角度分析一下：

92-代碼-1

代碼一：節(jié)點插入

public ListNode reverseBetween(ListNode head, int m, int n) {
    if(head == null) return null;
    // create a dummy node to mark the head of this list
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // make a pointer pre as a marker for the node before reversing
    ListNode pre = dummy;

    for(int i = 0; i<m-1; i++)
        pre = pre.next;

    // a pointer to the beginning of a sub-list that will be reversed
    ListNode start = pre.next;
    // a pointer to a node that will be reversed
    ListNode then = start.next;

    // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
    // dummy-> 1 -> 2 -> 3 -> 4 -> 5
    for(int i=0; i<n-m; i++){
        start.next = then.next;
        then.next = pre.next;
        pre.next = then;
        then = start.next;
    }
    // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
    // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
    return dummy.next;
}

92-代碼分析

首先博杖，我們利用給的 M 椿胯，找出第M個元素的位置，并將 M-1 位置標(biāo)記為 pre 欧募，M 標(biāo)記為 start 压状，M+1 位置標(biāo)記為 then 仆抵，然后執(zhí)行第二個循環(huán)跟继。
第二個循環(huán)的邏輯是交換節(jié)點种冬，但是，我們并不是交換相鄰的兩個元素舔糖，而是將 then 換到 pre.next 的位置娱两，這樣才能達到翻轉(zhuǎn)部分鏈表的目的：

1. 循環(huán)找到第 M 個元素

   
   
   第一次循環(huán)后
2. 將 then 換到 pre.next
   
   第二個循環(huán)執(zhí)行一次
3. 將then后移一個
   
   后移

4. 繼續(xù)循環(huán)

   
   

為了達到這個目的，我們要聲明三個指針

• 第一個指向最后一個不需要反轉(zhuǎn)的節(jié)點（第 M-1 個節(jié)點）金吗，相當(dāng)于要反轉(zhuǎn)鏈表部分的 dummy 十兢，它負責(zé)找到頭。
• 第二個指向第 M 個節(jié)點摇庙，它將是反轉(zhuǎn)鏈表部分的最后一個節(jié)點旱物，它負責(zé)找到尾。
• 以上這兩個指針不應(yīng)該移動卫袒，因為他們類似于 dummy 一頭一尾宵呛，可以確定翻轉(zhuǎn)邊界。
• 第三個指針循環(huán)中移動夕凝，來使鏈表翻轉(zhuǎn)宝穗。它負責(zé)元素移動。

92-代碼-2

代碼二：遞歸

class Solution {

    // Object level variables since we need the changes
    // to persist across recursive calls and Java is pass by value.
    private boolean stop;
    private ListNode left;

    public void recurseAndReverse(ListNode right, int m, int n) {

        // base case. Don't proceed any further
        if (n == 1) {
            return;
        }

        // Keep moving the right pointer one step forward until (n == 1)
        right = right.next;

        // Keep moving left pointer to the right until we reach the proper node
        // from where the reversal is to start.
        if (m > 1) {
            this.left = this.left.next;
        }

        // Recurse with m and n reduced.
        this.recurseAndReverse(right, m - 1, n - 1);

        // In case both the pointers cross each other or become equal, we
        // stop i.e. don't swap data any further. We are done reversing at this
        // point.
        if (this.left == right || right.next == this.left) {
            this.stop = true;
        }

        // Until the boolean stop is false, swap data between the two pointers
        if (!this.stop) {
            int t = this.left.val;
            this.left.val = right.val;
            right.val = t;

            // Move left one step to the right.
            // The right pointer moves one step back via backtracking.
            this.left = this.left.next;
        }
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        this.left = head;
        this.stop = false;
        this.recurseAndReverse(head, m, n);
        return head;
    }
}

92-代碼-3

代碼三：代碼復(fù)用
這個方法是將部分鏈表翻轉(zhuǎn)码秉，轉(zhuǎn)化為已知問題逮矛，也就是206轉(zhuǎn)化一個完整鏈表問題。這樣就可以將位置問題轉(zhuǎn)化為已知問題转砖，第二個循環(huán)完全是代碼的復(fù)用须鼎。

public ListNode reverseBetween(ListNode head, int m, int n) {
    // Empty list
    if (head == null) {
        return null;
    }
    // Move the two pointers until they reach the proper starting point
    // in the list.
    ListNode cur = head, prev = null;
    while (m > 1) {
        prev = cur;
        cur = cur.next;
        m--;
        n--;
    }

    // The two pointers that will fix the final connections.
    ListNode con = prev, tail = cur;

    // Iteratively reverse the nodes until n becomes 0.
    ListNode third = null;
    while (n > 0) {
        third = cur.next;
        cur.next = prev;
        prev = cur;
        cur = third;
        n--;
    }

    // Adjust the final connections as explained in the algorithm
    if (con != null) {
        con.next = prev;
    } else {
        head = prev;
    }

    tail.next = cur;
    return head;
}

總結(jié)

這次的講的是鏈表的翻轉(zhuǎn)，可以用的思路有

• 遞歸堪藐、回溯
• 循環(huán)插入

鏈表問題在面試中被提問的可能性很大莉兰，而且題目變化種類不多，希望每講一個問題礁竞，每個方法都記住糖荒。

更多關(guān)于鏈表的問題

更多關(guān)于鏈表的問題請轉(zhuǎn)到鏈表標(biāo)簽