[LeetCode] 024. Swap Nodes in Pairs

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



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.


解題邏輯與實作

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


迭代

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



程式碼

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        



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET