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.Leetcode 463 Island Perimeter

See also  Ruby LinkedList Class Tutorial: Implementation and Usage

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.

See also  Reverse Integer

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.

See also  Median of Two Sorted Arrays

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.

Written by

With 10+ years in software engineering, I specialize in blogging and web development. My skills span front-end, back-end, database design, web security, and SEO. Passionate about crafting helpful digital experiences.