24. Swap Nodes in Pairs
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Linked List、Recursion
一、題目
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Example 1:
- Input: head = [1,2,3,4]
- Output: [2,1,4,3]
Example 2:
- Input: head = []
- Output: []
Example 3:
- Input: head = [1]
- Output: [1]
Constraints:
- The number of nodes in the list in the range
[0, 100]. 0 <= Node.val <= 100
二、分析
- 經典的
ListNode問題，鏈表的後序遍歷，利用後序遍歷回傳值的特性並用recursion來完成這一題。
三、解題
1. Recursion
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head; // 先確定終止條件
ListNode* next = head->next; // 兩個節點為單位，所以在每一個遞迴內控制兩個節點
head->next = swapPairs(next->next); // 每個單位的尾巴接回傳值的頭部
next->next = head; // 實做每個單位裡面的反轉
return next; // 因為單位的尾巴要接到下一個單位的頭部，故這裡要回傳單位的頭位
}