【LeetCode】0024. Swap Nodes in Pairs

| | |

Given a linked list, swap every two adjacent nodes and return its head.

Example:

1
Given `1->2->3->4`, you should return the list as `2->1->4->3`.


Note:

  • Your algorithm should use only constant extra space.
  • You may not modify the values in the list’s nodes, only nodes itself may be changed.


Related Topics: Linked List

解題邏輯與實作

這題是要以兩個節點為一組翻轉鏈結串列，難度不高，但很容易把自己搞暈頭轉向，建議先畫圖輔助會比較清楚。

迭代

這個的想法比較簡單，就是兩兩指標交換，不過在交換時需要注意下交換的順序，不然很容易把指標搞丟了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
   def swapPairs(self, head):
      dummy_head = ListNode(-1)
      dummy_head.next = head
      iteration = dummy_head

      while iteration.next and iteration.next.next :
         node1 = iteration.next
         node2 = iteration.next.next

         iteration.next = node2
         node1.next = node2.next
         node2.next = node1

         iteration = iteration.next.next

      return dummy_head.next

遞迴

想說迭代做的到的，應該也可以用遞迴來實做。實做時，先交換最後兩個，再依序向前交換。

1
2
3
4
5
6
7
8
9
10
class Solution:
   def swapPairs(self, head):
      if not head or not head.next:
            return head

      node = head.next
      head.next = self.swapPairs(head.next.next)
      node.next = head

      return node

其他連結

  1. 【LeetCode】0000. 解題目錄