24. Swap Nodes in Pairs

發表於 分類於 ， 閱讀次數： 文章字數： 1.5k

種類 : linked list
難度 : medium
題目 : 24. Swap Nodes in Pairs

思維邏輯

1
2
3
4
5
6
7
8
9
10
graph LR
A[dummy_head]
B[10]
C[20]
D[30]
E[40]
A --> B
B --> C
C --> D
D --> E
  1. 使用虛擬head便於更改首個node位置
  2. 紀錄cur.next & cur.next.next
  3. 切換cur時，一次切換2個nodes
  4. 返回dummy_head.next

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        cur = dummy_head

        while cur.next and cur.next.next:
            tmp1 = cur.next
            tmp2 = cur.next.next.next

            cur.next = cur.next.next
            cur.next.next = tmp1
            tmp1.next = tmp2

            cur = cur.next.next

        return dummy_head.next

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. 一定要畫圖搭配步驟，否則容易亂‼️
  2. 在cur.next=cur.next.next前，需紀錄cur.next & cur.next.next
  3. 交換完一對nodes，切換為cur=cur.next.next
  4. 迴圈停止時機為cur.next == None & cur.next.next == None

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
✅ 較容易理解
使用雙指標當前與前一個node位置
"""
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(None, head)
        prev, cur = dummy, head
        while cur and cur.next:
            prev.next = cur.next      # dummy -> 20
            cur.next = cur.next.next  # 10 -> 30
            prev.next.next = cur      # 20 -> 10

            # 移動prev, cur
            prev = cur
            cur = cur.next
        return dummy.next

時間複雜度: O(n)
空間複雜度: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
遞迴
"""
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        # 待翻转的两个node分别是pre和cur
        pre = head
        cur = head.next
        next = head.next.next
        
        cur.next = pre  # 交换
        pre.next = self.swapPairs(next) # 将以next为head的后续链表两两交换
         
        return cur

時間複雜度: O(n)
空間複雜度: O(n)