【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. 解題目錄