Last Updated on 2022-02-16 by Clay
題目
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 is in the range
[0, 100]. 0 <= Node.val <= 100
簡單來說，將鏈結串列上的數值兩兩交換，如果不足雙數則不變。
解題思路
改變節點值（不符合題目要求）
這題我使用了比較浪費記憶體的方法。首先直接建立一個 vector，接著將鏈結串列跑到底，將每個值放入 vector 當中，接著將數值兩兩交換，再建立一個新的鏈結串列放入交換過後的值。
最簡單暴力的方法，應該沒有值得參考的地方。（應該說其實題目就告訴我們只能改變節點位置、不能改變節點值）
當然你也可以不要建立 vector，只是純粹將節點值做交換…… 不過當時亂寫亂寫，就乾脆憑第一感將其寫出來。
改變節點值時間複雜度
如果不建立陣列的話空間複雜度就是 O(1) 了…… 不過其實在改變節點時就已經不符合題意了。
| Time Complexity | O(n) |
| Space Complexity | O(n) |
改變節點值 C++ 程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// Base case
if (head == nullptr || head->next == nullptr) return head;
// Init
vector<int> nums;
ListNode* currNode = head;
// Get all values
while (currNode != nullptr) {
nums.push_back(currNode->val);
currNode = currNode->next;
}
// Swap
for (int i=0; i<nums.size(); ++i) {
if (i % 2 == 1) {
swap(nums[i-1], nums[i]);
}
}
// Change the values of the nodes
currNode = new ListNode(0, head);
for (int n: nums) {
currNode->next->val = n;
currNode = currNode->next;
}
return head;
}
};改變節點值 Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case
if not head or not head.next:
return head
# Init
nums = []
currNode = head
# Get all values
while currNode:
nums.append(currNode.val)
currNode = currNode.next
# Swap
for i in range(len(nums)):
if i % 2 == 1:
nums[i-1], nums[i] = nums[i], nums[i-1]
# Change the values of the nodes
currNode = ListNode(0, head)
for n in nums:
currNode.next.val = n
currNode.next = currNode.next.next
return head遞迴
這題其實可以使用遞迴來解，也確實符合題目所要求的不改變值。
先建立第二個節點的暫存節點，再將第一個節點指向輸入第三個節點的遞迴函式（使用本身的函式即可，代表著將第三個節點視為第一個節點，再重複做一次交換流程），接著將第二個節點指向第一個節點，最後直接回傳第二個節點（因為第二個節點此時已經是第一個節點了）。
遞迴時間複雜度
如果不建立陣列的話空間複雜度就是 O(1) 了…… 不過其實在改變節點時就已經不符合題意了。
| Time Complexity | O(n) |
| Space Complexity | O(1) |
遞迴 C++ 程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// Base case
if (head == nullptr || head->next == nullptr) return head;
// Init
ListNode* tempNode = head->next;
// Swap
head->next = swapPairs(head->next->next);
tempNode->next = head;
return tempNode;
}
};改變節點值 Python 範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Base case
if not head or not head.next:
return head
# Init
tempNode = head.next
# Swap
head.next = self.swapPairs(head.next.next)
tempNode.next = head
return tempNode