Sponsored
Sponsored
This approach uses iteration to systematically swap each pair of adjacent nodes in the linked list. The main idea is to traverse the list while keeping track of pointers to the nodes before and after the pair being swapped. By adjusting these pointers, we effectively swap nodes without modifying their values.
Time Complexity: O(n), where n is the number of nodes in the linked list. We process each node once.
Space Complexity: O(1), We are using constant extra space.
1class Solution {
2public:
3 ListNode* swapPairs(ListNode* head) {
4 ListNode dummy(-1);
5 dummy.next = head;
6 ListNode* prev = &dummy;
7
8 while (prev->next && prev->next->next) {
9 ListNode* a = prev->next;
10 ListNode* b = a->next;
11 a->next = b->next;
12 b->next = a;
13 prev->next = b;
14 prev = a;
15 }
16 return dummy.next;
17 }
18};This C++ solution follows the same logic as the C version. We utilize a dummy node to simplify pointer manipulation when swapping pairs of nodes. The main loop iteratively swaps pairs by adjusting pointers, ensuring the correct links are maintained.
The dummy node effectively shifts the responsibility of changing the head pointer to the structure itself instead of requiring separate logic, making the code cleaner.
This approach leverages recursion to swap every two adjacent nodes. The key idea is to break the problem into subproblems where you solve for a pair and recursively call to solve for the next. The recursion naturally handles the base case where less than two nodes remain to be swapped.
Time Complexity: O(n), every node is processed once.
Space Complexity: O(n), the call stack in recursive functions uses space proportional to the number of elements.
1
Java's recursive implementation involves a base case check to handle lists with fewer than two nodes, returning the head directly. For other cases, it initializes newHead as the second node in the current list, swaps links between head and head.next, and recursively calls the function to continue swapping further along the list, ensuring swaps complete correctly.