Swap Nodes in Pairs · 數據結構與算法/leetcode/lintcode題解

# Swap Nodes in Pairs ### Source - leetcode: [Swap Nodes in Pairs | LeetCode OJ](https://leetcode.com/problems/swap-nodes-in-pairs/) - lintcode: [(451) Swap Nodes in Pairs](http://www.lintcode.com/en/problem/swap-nodes-in-pairs/) ### Problem 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`. #### Challenge Your algorithm should use only constant space. You may not modify the valuesin the list, only nodes itself can be changed. ### 題解1 - Iteration 直覺上我們能想到的是使用 dummy 處理不定頭節點，但是由于這里是交換奇偶位置的鏈表節點，我們不妨首先使用偽代碼來表示。大致可以分為如下幾個步驟： 1. 保存`2.next` 1. 將`2.next`賦值為`1` 1. 將`1.next`賦值為1中保存的`2.next` 1. 將前一個鏈表節點的 next 指向`1` 1. 更新前一個鏈表節點為`1` 1. 更新當前的鏈表節點為1中保存的`2.next` 鏈表類題目看似容易，但要做到 bug-free 其實不容易，建議結合圖像輔助分析，onsite 時不要急，把過程先用偽代碼寫出來。然后將偽代碼逐行轉化。 ### Java ~~~ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { /** * @param head a ListNode * @return a ListNode */ public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy, curr = head; while (curr != null && curr.next != null) { ListNode after = curr.next; ListNode nextCurr = after.next; after.next = curr; curr.next = nextCurr; // link new node after prev prev.next = after; // update prev and curr prev = curr; curr = nextCurr; } return dummy.next; } } ~~~ ### 源碼分析這里使用 dummy 處理不定頭節點，首先將`prev`初始化為`dummy`, 然后按照題解中的幾個步驟逐步轉化，需要注意的是 while 循環中`curr`和`curr.next`都不能為`null`. ### 復雜度分析遍歷鏈表一遍，時間復雜度 O(1)O(1)O(1). 使用了若干臨時鏈表節點引用對象，空間復雜度 O(1)O(1)O(1). ### 題解2 - Recursion 在題解1 的分析過程中我們發現比較難處理的是 `prev`和下一個頭的連接，要是能直接得到鏈表后面新的頭節點該有多好啊。首先我們可以肯定的是若`head == null || head.next == null`時應直接返回，如果不是則求得交換奇偶節點后的下一個頭節點并鏈接到之前的奇數個節點。這種思想使用遞歸實現起來非常優雅！ ### Java ~~~ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { /** * @param head a ListNode * @return a ListNode */ public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode after = head.next; head.next = swapPairs(after.next); after.next = head; return after; } } ~~~ ### 源碼分析這個遞歸實現非常優雅，需要注意的是遞歸步的退出條件==>`head == null || head.next == null)`. ### 復雜度分析每個節點最多被遍歷若干次，時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1).