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:
2 def swapPairs(self, head: ListNode) -> ListNode:
3 dummy = ListNode(0)
4 dummy.next = head
5 prev = dummy
6
7 while prev.next and prev.next.next:
8 a = prev.next
9 b = a.next
10 a.next = b.next
11 b.next = a
12 prev.next = b
13 prev = a
14
15 return dummy.nextThis Python solution also leverages a dummy node to conveniently handle potential changes to the head node. The prev pointer iterates through the list, and within the loop, pointers are reassigned to swap each pair of nodes, making sure to continue the swap process with prev set at the end of the current pair.
Python's dynamic typing and straightforward list node management makes this implementation quite elegant and succinct.
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
The Python function checks if there are fewer than two nodes left, returning the head. It takes head.next, which is the new head in the swapped pair, and performs a recursive call on the list starting after the next node, setting the returned result to head.next.
This recursive setup effectively 'switches' the pairs and uses the call stack to finish the swaps for the entire list.