Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes. Only nodes itself 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
Swap every two adjacent nodes in pairs in a singly linked list, and return its new head.
For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
Swap Values
Just swap the values of two nodes, this saves hassles of swapping pointers and this should be the most straightforward solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { auto p = head; if (p == NULL) { return p; } while (p && p->next) { swap(p->val, p->next->val); p = p->next->next; // next pair } return head; // head doesn't change } }; |
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
auto p = head;
if (p == NULL) {
return p;
}
while (p && p->next) {
swap(p->val, p->next->val);
p = p->next->next; // next pair
}
return head; // head doesn't change
}
};Swap Nodes
However, if we go for swapping the nodes, we have to take care of the new *head*, and the pointer swapping isn’t fun.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Solution { public: ListNode* swapPairs(ListNode* head) { auto p = head; if (p == NULL) { return p; } if (p && p->next) { // swap the first two nodes auto next = p->next; p->next = p->next->next; next->next = p; head = next; // record new *head* } else { return head; // only 1 node } auto prev = head->next; p = head->next->next; while (p && p->next) { // the rest pairs auto next = p->next; p->next = p->next->next; next->next = p; prev->next = next; prev = p; p = p->next; } return head; } }; |
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
auto p = head;
if (p == NULL) {
return p;
}
if (p && p->next) { // swap the first two nodes
auto next = p->next;
p->next = p->next->next;
next->next = p;
head = next; // record new *head*
} else {
return head; // only 1 node
}
auto prev = head->next;
p = head->next->next;
while (p && p->next) { // the rest pairs
auto next = p->next;
p->next = p->next->next;
next->next = p;
prev->next = next;
prev = p;
p = p->next;
}
return head;
}
};Both solutions have time complexity O(n) and the space complexity O(1).
Swap Nodes in Pairs using Recursion
We can use Recursive algorithm to do this. We need to first swap the first two, then the rest can be done recursively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /** * 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) { if (!head) return NULL; if (!head->next) return head; auto newHead = head->next; auto next = newHead->next; newHead->next = head; head->next = swapPairs(next); return newHead; } }; |
/**
* 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) {
if (!head) return NULL;
if (!head->next) return head;
auto newHead = head->next;
auto next = newHead->next;
newHead->next = head;
head->next = swapPairs(next);
return newHead;
}
};The time and space complexity is O(N).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Review: Lenovo ThinkCenter M900 Tower Station
Next Post: Algorithms to Merge Two Sorted Array