1 題目描述

簡單來說，就是在指定的位置 m 到 n 之間，將鍊錶進行反轉。

注意的是，題目要 one pass 是指只能遍歷一次鍊錶，不能多次遍歷。

2 解法

2.1 我的解法

我的想法很簡單

  1. 先建立一個字典，紀錄 key = index, value = node
  2. 你會發現 left 到 right 之間的反轉，從 left 開始，left 應該改成 right 的值，right 應該改成 left 的值，直到 left 跟 right 相遇。
  3. 何時該停呢？當 left >= 原本的 right 時，就停止。

大概是這種感覺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def reverseBetween(
            self,
            head: Optional[ListNode],
            left: int,
            right: int) -> Optional[ListNode]:
        if left == right:
            return head

        # 1. build up dictionary
        node_dict = {}

        index = 1
        cur = head
        while cur:
            node_dict.__setitem__(index, cur)
            cur = cur.next
            index += 1

        # 2 開始反轉把 left 的位置變成 right 的位置
        org_right = right
        dummy = ListNode()
        cur = dummy
        index = 0
        while cur:
            if index == left - 1 and left <= org_right:
                cur.next = node_dict.get(right) # 關鍵在這裡，把 left 的位置變成 right 的位置
                left += 1
                right -= 1
            else: 
                cur.next = node_dict.get(index + 1) # 一般情況下，就是把原本的鍊錶串起來

            index += 1
            cur = cur.next

        ans = dummy.next
        dummy.next = None
        return ans

2.2 雙指針解法

這個做法真的是從來沒想過，但是很巧妙，而且只需要遍歷一次鍊錶，就可以完成反轉。超級厲害！
他的概念是這樣的:

  1. 先找到 pre 這個節點
    • 怎麼找到pre? 這個節點是 left 的前一個節點，也就是 left - 1，之後就都固定 pre 不動。
    • 為什麼需要？ 因為 pre 要負責更新 pre.next 為反轉後的第一個節點。
  2. 再來就是 cur 這個節點，
    • 怎麼找到 cur? 最一開始，cur 是 pre.next，之後就固定 cur 不動。
    • 為什麼需要? 因為 cur 要負責更新 cur.next 為 next.next 這個節點，往前移動。
  3. 最後是 next 這個節點
    • 怎麼找到 next? 最一開始，next 是 cur.next，之後就固定 next 不動。
    • 為什麼需要? 因為 next 要負責更新 next.next 為 cur 這個節點，往前移動。

大概是這種感覺，你會發現 next 會被塞到 pre.next 這個位置，而 cur 就一直往前移動

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverseBetween2(
            self,
            head: Optional[ListNode],
            left: int,
            right: int) -> Optional[ListNode]:

        dummy = ListNode(0, head)
        pre_n = dummy
        for _ in range(left-1):
            pre_n = pre_n.next

        cur_n = pre_n.next
        for _ in range(right - left):
            next_n = cur_n.next
            cur_n.next = next_n.next
            next_n.next = pre_n.next
            pre_n.next = next_n

        return dummy.next

3 總結

這題不難理解，凡是想要從 O(n^2) 變成 O(n) 可以使用 HashMap，所以我一開始就建立字典記錄所有的位置。但是後來看到雙指針解法，真的是很厲害，腦袋到底怎麼想到的啊！
如果今天要有順序的進行反轉或是整批的改變位置移動，雙指針會是一個Linked List的重點。想像有兩個指針，一個指針cur慢往前，另一個指針會是目標節點target (在這裡是next)，target 會串到想要放的目標 location(在這裡是pre.next)，cur 會一直往前移動(cur.next 變成 pre.next)，直到達到目標節點，這樣就可以完成操作。