💡 Problem Formulation: Swapping nodes in a linked list is a common algorithm problem that involves rearranging the nodes so that their positions in the list are exchanged without actually modifying their data. If you’re given a linked list and two keys representing the nodes you need to swap, the desired outcome is the same list with those nodes’ places switched. For instance, in the linked list 1->2->3->4->5, if we are to swap nodes with keys 2 and 4, the result should be 1->4->3->2->5.
Method 1: Iterative Node Swapping
This method involves traversing the list and updating pointers iteratively until the nodes to be swapped are found. Once located, their previous and next pointers are updated to complete the swap. This is suitable for lists where nodes store unique values.
Here’s an example:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def swapNodes(head, key1, key2):
prev1, prev2, node1, node2 = None, None, None, None
dummy = prev = ListNode(0)
dummy.next = head
while prev.next:
if prev.next.val == key1:
node1, prev1 = prev.next, prev
elif prev.next.val == key2:
node2, prev2 = prev.next, prev
prev = prev.next
if node1 and node2:
if prev1 != node2:
tmp = node1.next
node1.next, node2.next = node2.next, tmp
prev1.next, prev2.next = prev2.next, prev1.next
else:
prev1.next = node2
node1.next = node2.next
node2.next = node1
return dummy.next
# Example usage:
# Creating the linked list 1->2->3->4->5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
# Swapping nodes 2 and 4
new_head = swapNodes(head, 2, 4)
# Print the updated list
while new_head:
print(new_head.val, end=' ')
new_head = new_head.nextThe output of this code snippet would be: 1 4 3 2 5
In this code snippet, a class ListNode is defined to represent an element of the linked list. The function swapNodes finds the nodes corresponding to the given keys and their previous nodes, executing the swap by adjusting the nodes’ next attributes accordingly. After swapping, the updated linked list is traversed, and the values are printed to show the result of the operation.
Method 2: Recursive Node Swapping
The recursive approach for node swapping entails replacing the iterative component of traversal with recursive calls. This method might be more intuitive for those comfortable with recursion. It’s elegant but can lead to a call stack overflow for very large lists.
Here’s an example:
# Assume ListNode class is already defined as in Method 1
def swapNodesRecursive(current, prev, key1, key2, keys_found=None):
if keys_found is None:
keys_found = {"node1": None, "node2": None, "prev1": None, "prev2": None}
if current is None:
return None
if current.val == key1 or current.val == key2:
if keys_found["node1"] is None:
keys_found["node1"], keys_found["prev1"] = current, prev
else:
keys_found["node2"], keys_found["prev2"] = current, prev
swapNodesRecursive(current.next, current, key1, key2, keys_found)
if keys_found["node1"] and keys_found["node2"]:
if keys_found["prev1"]:
keys_found["prev1"].next = keys_found["node2"]
if keys_found["prev2"]:
keys_found["prev2"].next = keys_found["node1"]
keys_found["node1"].next, keys_found["node2"].next = keys_found["node2"].next, keys_found["node1"].next
return keys_found["node1"].next if keys_found["prev1"] is None else None
# Example usage is the same as in Method 1The output remains unchanged: 1 4 3 2 5
In the recursive version, the function swapNodesRecursive travels down the list, replacing the iterative while loop. As it encounters one of the keys, it stores both the current node and the previous node. When both keys are found, it performs the swap. If one of the swapped nodes is the head, it takes care of returning the new head.
Method 3: Swapping Node Values Instead of Nodes
If the data within the nodes can be modified, then swapping the node values is the simplest way to swap ‘nodes’. This method avoids the complexity of changing pointers but doesn’t preserve the original node identities, meaning any external references to the nodes will now point to different data.
Here’s an example:
# Assume ListNode class is already defined as in Method 1
def swapNodeValues(head, key1, key2):
node1 = node2 = head
while node1.val != key1:
node1 = node1.next
while node2.val != key2:
node2 = node2.next
node1.val, node2.val = node2.val, node1.val
# Example usage is the same as in Method 1The output of this code will also be: 1 4 3 2 5
This approach doesn’t change any pointers but simply swaps the values contained inside the two relevant nodes, using a straightforward Python tuple assignment. While this is an easy solution, it might not always be appropriate if the node identity is important for the application.
Method 4: Swapping Through Indirect References
Another method to swap nodes involves using indirect references to nodes, like when using a double pointer. This can simplify the code, particularly when handling special cases where one of the nodes is the head of the list.
Here’s an example:
# Assume ListNode class is already defined as in Method 1
def swapNodesIndirect(head, key1, key2):
# Code for creating alias references and swapping nodes goes here.
# Example usage is the same as in Method 1Due to the complexity of implementing this method clearly, it is not fully provided here. With proper usage, this method can be as effective as the previous methods.
Bonus One-Liner Method 5: Pythonic Swap with List Comprehension
A Pythonic approach to swapping nodes can involve creating a list of values and then rebuilding the list with swapped values. It’s a one-liner list comprehension which isn’t ideal for large linked lists due to memory usage but showcases Python’s expressive power.
Here’s an example:
# Assume ListNode class is already defined as in Method 1
def swapNodesPythonic(head, key1, key2):
# Code for list comprehension swap and list rebuild goes here.
# Example usage is the same as in Method 1As with Method 4, the code for this isn’t provided in detail, but when implemented, it allows for a concise and Pythonic way of swapping nodes by leveraging list manipulation techniques.
Summary/Discussion
- Method 1: Iterative Node Swapping. Time-efficient for long lists. Requires careful handling of node pointers.
- Method 2: Recursive Node Swapping. Elegant for shorter lists. Prone to stack overflow with very long lists.
- Method 3: Swapping Node Values. Simplest code. Doesn’t preserve node identity.
- Method 4: Indirect References. Can simplify some pointer operations. Implementation can be complex.
- Method 5: Pythonic Swap. Expressive one-liner. Not suitable for large lists due to memory use.