Example:

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

解題邏輯與實作

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

迭代

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

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        

遞迴

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

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

本文作者： 辛西亞．Cynthia
本文連結： 辛西亞的技能樹 / hackmd 版本
版權聲明： 部落格中所有文章，均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！