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)的頻率，因?yàn)檫@個(gè)92題是II，206才是I。所以我們主要分析這道題。無(wú)非就是給你兩個(gè)數(shù)，讓你翻轉(zhuǎn)第 M 個(gè)到底 N 個(gè)鏈表上的元素。

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

92-代碼-1

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

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個(gè)元素的位置，并將 M-1 位置標(biāo)記為 pre ，M 標(biāo)記為 start ，M+1 位置標(biāo)記為 then ，然后執(zhí)行第二個(gè)循環(huán)。
第二個(gè)循環(huán)的邏輯是交換節(jié)點(diǎn)，但是，我們并不是交換相鄰的兩個(gè)元素，而是將 then 換到 pre.next 的位置，這樣才能達(dá)到翻轉(zhuǎn)部分鏈表的目的：

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

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

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

   
   

為了達(dá)到這個(gè)目的，我們要聲明三個(gè)指針

• 第一個(gè)指向最后一個(gè)不需要反轉(zhuǎn)的節(jié)點(diǎn)（第 M-1 個(gè)節(jié)點(diǎn)），相當(dāng)于要反轉(zhuǎn)鏈表部分的 dummy ，它負(fù)責(zé)找到頭。
• 第二個(gè)指向第 M 個(gè)節(jié)點(diǎn)，它將是反轉(zhuǎn)鏈表部分的最后一個(gè)節(jié)點(diǎn)，它負(fù)責(zé)找到尾。
• 以上這兩個(gè)指針不應(yīng)該移動(dòng)，因?yàn)樗麄冾愃朴?dummy 一頭一尾，可以確定翻轉(zhuǎn)邊界。
• 第三個(gè)指針循環(huán)中移動(dòng)，來(lái)使鏈表翻轉(zhuǎn)。它負(fù)責(zé)元素移動(dòng)。

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ù)用
這個(gè)方法是將部分鏈表翻轉(zhuǎn)，轉(zhuǎn)化為已知問(wèn)題，也就是206轉(zhuǎn)化一個(gè)完整鏈表問(wèn)題。這樣就可以將位置問(wèn)題轉(zhuǎn)化為已知問(wèn)題，第二個(gè)循環(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)插入

鏈表問(wèn)題在面試中被提問(wèn)的可能性很大，而且題目變化種類不多，希望每講一個(gè)問(wèn)題，每個(gè)方法都記住。

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

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