反轉連結清單(二)JAVA

反轉清單（二）

題目描述

• 反轉從位置 m 到 n 的連結清單。請使用一趟掃描完成反轉。

• 說明:

  1 ≤ m ≤ n ≤ 連結清單長度。

• 示例:

  輸入: 1->2->3->4->5->NULL, m = 2, n = 4

  輸出: 1->4->3->2->5->NULL

題解(java)

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        // 判斷是否為空連結清單
        if (head == null) {
            return null;
        }

         
        ListNode cur = head;
        ListNode prev = null;
        //把 prev 和 cur移到頭斷點兩側
        while (m > 1) {
            prev = cur;
            cur = cur.next;
            m--;
            n--;
        }

       //并記為 con 和 tail
        ListNode con = prev, tail = cur;

        // 繼續移動 prev 和 cur 到尾斷點兩側
        while (n > 0) {
            ListNode third = cur.next;
            cur.next = prev;
            prev = cur;
            cur = third;
            n--;
        }

        // 從新連接配接
        //要考慮到從第一節點開始反轉的情況
        if (con != null) {
            con.next = prev;
        } else {
            head = prev;
        }

        tail.next = cur;
        return head;
    }
}
           

圖示

詳解

-.簡單來說，該題的目的為反轉連結清單中的其中一段節點，那麼我們隻要分别找到頭斷點和尾斷點兩側的端點，再重新連接配接這四個端點即可（特殊情況，從第一個節點開始反轉）

-1>.首先定義一個空指針 prev 指向 nul，以及指針 cur 指向 head這兩個指針一起同步向後移動，直到找到頭斷點的位置，因為在初始時，cur 正好為 m = 1 處，是以當 m>1 時，兩節點開始移動。

• 2>找到位置後，将 con 定位指向 prev，tail 定位指向 cur,在繼續順移直到找到尾斷點，其中 prev 和 cur 分别位于尾斷點兩側。
• 3>.頭斷點和尾斷點的位置都找到後，因為在移動的過程中，我們已經反轉了該部分的連結清單，是以隻需将連結清單重新連接配接即可【con 連接配接 prev, tail 連接配接 cur】
• 4>.連接配接完畢後，傳回新的連結清單即可

Tips

• 解釋為什麼找頭斷點周遊條件為 m>1 ,找尾斷點便利條件為 n>0：因為找頭斷點時，prev指向的是需反轉區間的連結清單的頭結點，找尾斷電時，prev指向的是該區間連結清單尾節點之後的那個節點。
• 注意：有一種特殊情況為連結清單中的第一個節點也在需反轉的範圍内，這時隻需重新令尾斷點前的尾節點為新的頭結點，再使 tail 連接配接 cur 即可得到新的連結清單
• 注意：在開始操作之前還是要判斷該連結清單是否為空連結清單。

難點

• 多個指針的複雜操作

聲明

• 原作者E.L.E
• <本文章著作權歸作者所有，商業轉載請獲得作者授權，非商業轉載請注明出處>
• <歡迎大家評論>