Swap Nodes

 Let's explore the concept of swapping nodes in a linked list using Python. We'll start by explaining the topic thoroughly, provide an example with proper comments, and then solve a question from LeetCode that involves swapping nodes in a linked list. We'll also analyze the time and space complexity of our solution.

  1. Swapping Nodes in a Linked List: Swapping nodes in a linked list involves changing the positions of two nodes within the list. This operation is commonly used in various linked list problems to rearrange elements or modify the structure of the list.

The process typically includes identifying the nodes to be swapped, adjusting the pointers of the preceding and succeeding nodes, and updating the head or tail pointers if necessary. Swapping can be done by directly modifying the pointers or by swapping the values between the nodes.

  1. Example with Comments: Let's demonstrate the swapping of nodes in a linked list with an example. Consider the following linked list:

1 -> 2 -> 3 -> 4 -> 5

We'll swap the nodes containing the values 2 and 4, resulting in the following linked list:


1 -> 4 -> 3 -> 2 -> 5

Here's the Python code with step-by-step comments explaining each operation:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def swapNodes(head, val1, val2):
    # Initialize pointers to keep track of the nodes to be swapped and their preceding nodes
    node1, node2 = None, None
    prev1, prev2 = None, None

    # Traverse the linked list to find the nodes and their preceding nodes
    curr = head
    while curr:
        if curr.val == val1:
            node1 = curr
            break
        prev1 = curr
        curr = curr.next

    curr = head
    while curr:
        if curr.val == val2:
            node2 = curr
            break
        prev2 = curr
        curr = curr.next

    # Handle the case when either node1 or node2 is not found
    if not node1 or not node2:
        return head

    # Adjust the pointers to swap the nodes
    if prev1:
        prev1.next = node2
    else:
        head = node2
    if prev2:
        prev2.next = node1
    else:
        head = node1
    node1.next, node2.next = node2.next, node1.next

    return head


# Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
node2 = head.next = ListNode(2)
node3 = node2.next = ListNode(3)
node4 = node3.next = ListNode(4)
node5 = node4.next = ListNode(5)

# Swap nodes 2 and 4
head = swapNodes(head, 2, 4)

# Print the resulting linked list: 1 -> 4 -> 3 -> 2 -> 5
curr = head
while curr:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

The swapNodes function takes the head of a linked list and the values of the nodes to be swapped as input. It traverses the linked list to find the nodes and their preceding nodes. Then, it adjusts the pointers to swap the nodes.

  1. Solving a LeetCode Problem: "Swap Nodes in Pairs" Now, let's solve a question from LeetCode that involves swapping nodes in a linked list.

Problem: "Swap Nodes in Pairs" Given a linked list, swap every two adjacent nodes and return its head.

You can find the problem details and constraints here: https://leetcode.com/problems/swap-nodes-in-pairs/

Here's the complete code for solving the "Swap Nodes in Pairs" problem:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def swapPairs(head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head and head.next:
        # Nodes to be swapped
        first = head
        second = head.next

        # Swap the nodes
        prev.next = second
        first.next = second.next
        second.next = first

        # Update pointers for the next iteration
        prev = first
        head = first.next

    return dummy.next


# Example usage
# Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
node2 = head.next = ListNode(2)
node3 = node2.next = ListNode(3)
node4 = node3.next = ListNode(4)
node5 = node4.next = ListNode(5)

# Swap nodes in pairs
head = swapPairs(head)

# Print the resulting linked list: 2 -> 1 -> 4 -> 3 -> 5
curr = head
while curr:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

The swapPairs function takes the head of a linked list as input and swaps every two adjacent nodes. It uses a dummy node and three pointers to perform the swapping.

  1. Time and Space Complexity Analysis: The time complexity of the swapNodes function is O(N), where N is the number of nodes in the linked list. This is because we need to traverse the list to find the nodes to be swapped.

The space complexity is O(1) since we are not using any additional data structures that grow with the input size.

For the "Swap Nodes in Pairs" problem, the time complexity is also O(N) since we traverse the list once. The space complexity remains O(1) as we only use a constant amount of extra space.

By understanding the concept of swapping nodes in a linked list and implementing the necessary logic, we can efficiently solve problems that involve rearranging or modifying the structure of linked lists.

 

 

Next Post Previous Post