Swapping nodes in a linked list means exchanging the positions of two nodes in the list. For example, if we have a linked list 1 -> 2 -> 3 -> 4 -> 5 and we want to swap the second and fourth nodes, the result will be 1 -> 4 -> 3 -> 2 -> 5.
Swapping nodes can be a bit tricky in singly linked lists because we need to update the pointers of the nodes before and after the swapped nodes. However, it is relatively easier in doubly or circular linked lists because we have access to both the previous and next nodes of each node.
Here is a nonrecursive solution for swapping two nodes in a doubly linked list:
function swapNodes(node1, node2):
if node1 is the same as node2:
return
tempPrev1 = node1.prev
tempNext1 = node1.next
tempPrev2 = node2.prev
tempNext2 = node2.next
if tempNext1 is the same as node2:
# node1 is immediately before node2
node1.prev = node2
node1.next = tempNext2
node2.prev = tempPrev1
node2.next = node1
tempNext2.prev = node1
tempPrev1.next = node2
elif tempPrev2 is the same as node1:
# node2 is immediately before node1
node2.prev = node1
node2.next = tempNext1
node1.prev = tempPrev2
node1.next = node2
tempNext1.prev = node2
tempPrev2.next = node1
else:
# nodes are not adjacent
node1.prev = tempPrev2
node1.next = tempNext2
node2.prev = tempPrev1
node2.next = tempNext1
tempNext2.prev = node1
tempPrev1.next = node2
tempNext1.prev = node2
tempPrev2.next = node1
In this pseudocode, we first check if the two nodes are the same. If they are, we simply return. Then, we store the previous and next nodes of both nodes in temporary variables. We need these variables because we’ll be updating the pointers of the nodes, and we don’t want to lose the connections.
Next, we check if the two nodes are adjacent. If they are, we update the pointers of the nodes accordingly. Otherwise, we update the pointers of all the relevant nodes.
Here is a recursive solution for swapping two nodes in a doubly linked list:
function swapNodes(node1, node2):
if node1 is the same as node2:
return
if node1.next is the same as node2:
# node1 is immediately before node2
tempPrev = node1.prev
tempNext2 = node2.next
node1.prev = node2
node1.next = tempNext2
node2.prev = tempPrev
node2.next = node1
tempNext2.prev = node1
if tempPrev is not None:
tempPrev.next = node2
elif node2.next is the same as node1:
# node2 is immediately before node1
tempPrev = node2.prev
tempNext1 = node1.next
node2.prev = node1
node2.next = tempNext1
node1.prev = tempPrev
node1.next = node2
tempNext1.prev = node2
if tempPrev is not None:
tempPrev.next = node1
else:
# nodes are not adjacent
tempPrev1 = node1.prev
tempNext1 = node1.next
tempPrev2 = node2.prev
tempNext2 = node2.next
node1.prev = tempPrev2
node1.next = tempNext2
node2.prev = tempPrev1
node2.next = tempNext1
if tempPrev1 is not None:
tempPrev1.next = node2
if tempPrev2 is not None:
tempPrev2.next = node1
if tempNext1 is not None:
tempNext1.prev = node2
if tempNext2 is not None:
tempNext2.prev = node1
swapNodes(node2, node1.next)
This recursive pseudocode works similarly to the iterative pseudocode for a double linked list. However, instead of using loops, we use recursive function calls to traverse the list and swap nodes. The function swaps the current pair of nodes and then calls itself with the next pair of nodes.
Note that the function assumes that the linked list has a prev pointer in addition to the next pointer.
Note that the above pseudocode assumes that the linked list has a prev pointer in addition to the next pointer. If the linked list is singly linked, we would need to traverse the list to find the nodes before the nodes we want to swap, in order to update their pointers.
Here is a nonrecursive solution for swapping a node in a singly linked list
function swapNodes(node1, node2, head):
if node1 is the same as node2:
return head
prev1 = None
curr1 = head
while curr1 is not None and curr1 is not node1:
prev1 = curr1
curr1 = curr1.next
prev2 = None
curr2 = head
while curr2 is not None and curr2 is not node2:
prev2 = curr2
curr2 = curr2.next
if curr1 is None or curr2 is None:
return head
if prev1 is not None:
prev1.next = curr2
else:
head = curr2
if prev2 is not None:
prev2.next = curr1
else:
head = curr1
temp = curr1.next
curr1.next = curr2.next
curr2.next = temp
return head
In this pseudocode, we first check if the two nodes are the same. If they are, we simply return the head of the list. Then, we traverse the list to find the nodes before the nodes we want to swap. We need these nodes in order to update their next pointers.
Next, we check if either of the nodes is not found in the list. If that’s the case, we simply return the head of the list.
If both nodes are found, we update the next pointers of the nodes before the nodes we want to swap. If the node to be swapped is the first node, we update the head of the list. Then, we swap the next pointers of the nodes to complete the swap.
Finally, we return the head of the list.
Here is a recursive solution for swapping a node in a singly linked list
function swapNodes(node1, node2, head):
if node1 is the same as node2:
return head
if head is the same as node1:
head = node2
elif head is the same as node2:
head = node1
prev1 = None
curr1 = head
while curr1 is not None and curr1 is not node1:
prev1 = curr1
curr1 = curr1.next
prev2 = None
curr2 = head
while curr2 is not None and curr2 is not node2:
prev2 = curr2
curr2 = curr2.next
if curr1 is None or curr2 is None:
return head
if prev1 is not None:
prev1.next = node2
if prev2 is not None:
prev2.next = node1
temp = node1.next
node1.next = node2.next
node2.next = temp
if prev1 is None:
head = node2
elif prev2 is None:
head = node1
swapNodes(node2.next, node1, head)
return head
This recursive pseudocode works similarly to the iterative pseudocode for a singly linked list, but instead of using loops, we use recursive function calls to traverse the list and swap nodes. The function swaps the current pair of nodes and then calls itself with the next pair of nodes.
Note that the function assumes that the nodes in the linked list have a next pointer that points to the next node in the list. It also takes the head of the list as an argument and returns the new head after swapping the nodes.
In both cases, the recursive approach can be less efficient than the iterative approach, especially for large lists, because it incurs the overhead of function calls on the call stack. However, it can be a useful tool in certain situations, such as when the list is very large and a recursive solution can simplify the code.
