Problem Statement:
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.)
Examples:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Input: head = []
Output: []
Input: head = [1]
Output: [1]
Constraints:
- The number of nodes in the list is in the range [0, 100].
- 0 ≤ Node.val ≤ 100
Approach (Recursive):
- Base case: if the list is empty or has only one node, return the head.
- Let
lbe the first node andrbe the second. - Call
swapPairsrecursively for the rest of the list starting fromr.next. - Set
l.nextto the result of recursive call. - Make
rpoint toland returnras the new head.
Time and Space Complexity:
- Time Complexity: O(n), where n is the number of nodes in the list.
- Space Complexity: O(n) due to recursive call stack.
var swapPairs = function(head) {
if (!head || !head.next) return head;
let l = head;
let r = head.next;
l.next = swapPairs(r.next);
r.next = l;
return r;
};
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode* first = head;
ListNode* second = head->next;
first->next = swapPairs(second->next);
second->next = first;
return second;
}
};
struct ListNode* swapPairs(struct ListNode* head) {
if (!head || !head->next) return head;
struct ListNode* first = head;
struct ListNode* second = head->next;
first->next = swapPairs(second->next);
second->next = first;
return second;
}
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
}
class Solution(object):
def swapPairs(self, head):
if not head or not head.next:
return head
first = head
second = head.next
first.next = self.swapPairs(second.next)
second.next = first
return second
public class Solution {
public ListNode SwapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode first = head;
ListNode second = head.next;
first.next = SwapPairs(second.next);
second.next = first;
return second;
}
}
