題目
#

leetcode 92 - Reverse Linked List II(題目說明請點連結)

題目簡述
#

給定一個鏈表和兩個整數 left 和 right，反轉從位置 left 到位置 right 的鏈表節點，並返回反轉後的鏈表。

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Explanation: 從位置 2 到位置 4 反轉鏈表，得到 [1,4,3,2,5]。

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: 只有一個節點，反轉後仍然是 [5]。

解題思路
#

這題給定一個 linked list 與 left、right。
回傳從left到right reverse 後的 linked list。

比如 1->2->3->4->5 left = 2 , right = 4
回傳的答案就是 1->4->3->2->5

這題我們將每一次的反轉進行逐步交換即可。

例子說明
#

head = [1,2,3,4,5], left = 2, right = 4

首先建立一個 dummy 作為避免 head 被反轉找不到沒有人指向第一個節點的情況，

初始情況：dummy -> 1 -> 2 -> 3 -> 4 -> 5
- prev：dummy（指向dummy，值為0）
- cur：1（指向head，值為1）
- temp：暫無

找到反轉起始位置：
- prev 移動到節點 1（left-1 = 1），此時 prev 指向1
- cur 指向節點 2（left = 2），此時 cur 指向2
- temp：暫無
- 狀態：dummy -> 1(prev) -> 2(cur) -> 3 -> 4 -> 5
第一次交換：
- temp = cur.next = 3，此時 temp 指向3
- cur.next = temp.next = 4，2的next指向4
- temp.next = prev.next = 2，3的next指向2
- prev.next = temp = 3，1的next指向3
- 交換後指針狀態：
  - prev：1
  - cur：2
  - temp：3
- 結果：dummy -> 1(prev) -> 3(temp) -> 2(cur) -> 4 -> 5
第二次交換：
- temp = cur.next = 4，此時 temp 指向4
- cur.next = temp.next = 5，2的next指向5
- temp.next = prev.next = 3，4的next指向3
- prev.next = temp = 4，1的next指向4
- 交換後指針狀態：
  - prev：1
  - cur：2
  - temp：4
- 結果：dummy -> 1(prev) -> 4(temp) -> 3 -> 2(cur) -> 5
完成反轉：
- 返回 dummy.next，即 [1,4,3,2,5]
- 此時 prev 仍指向1，cur指向2，temp指向4，反轉區間已完成

完整程式碼
#

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) { // 邊界條件：空鏈表或left等於right
            return head;
        }
        ListNode dummy = new ListNode(0); // 創建虛擬頭節點
        dummy.next = head; // 將虛擬頭節點連接到原鏈表
        ListNode prev = dummy; // 初始化prev指針

        for(int i = 1; i < left; i++) { // 移動prev到left位置的前一個節點
            prev = prev.next;
        }
        ListNode cur = prev.next; // cur指向left位置的節點

        for(int i = 0; i < right - left; i++) { // 執行right-left次交換
            ListNode temp = cur.next; // 暫存cur的下一個節點
            cur.next = temp.next; // 將cur的next指向temp的下一個節點
            temp.next = prev.next; // 將temp的next指向prev的下一個節點
            prev.next = temp; // 將prev的next指向temp
        }

        return dummy.next; // 返回虛擬頭節點的下一個節點
    }
}