CODEWITHSUNDEEP
algorithmdata-structuressingly-linked-list
Taelung
Taelung

Reputation: 1

linked list, swap nodes

I am trying to solve swap node in pairs (linked list). I have the correct code, but I am stucked while interpreting swapping step.

here is the code:

def swapPairs(head):
    pre = ListNode(0)
    pre.next = head

    while pre.next and pre.next.next:
        a = pre.next
        b = a.next
        pre.next, b.next, a.next = b, a, b.next
        pre = a

    return pre.next

for example, if my linked list is 1->2->3->4. Initially a is pointing to 1, and b to 2. During the swapping step: how do we not lose the linked list after 2? because b.next will point to a before we actually do a.next = b.next?

Upvotes: 0

Views: 85

Answers (2)

Ankit Chauhan
Ankit Chauhan

Reputation: 1

You're right to focus on the swapping step, as it can be tricky at first glance. Let me break it down for you.

Your key line of code is:

pre.next, b.next, a.next = b, a, b.next Let's go step by step through what happens:

Initial Setup:

a is pointing to the first node (in your example, 1). b is pointing to the second node (2). Before the swap, the linked list looks like this:

pre -> 1 (a) -> 2 (b) -> 3 -> 4 Swapping Process: The line:

pre.next, b.next, a.next = b, a, b.next does three things at once:

pre.next = b: This makes pre point to b, so now b is the first node in the pair:

pre -> 2 (b) -> 1 (a) -> 3 -> 4 b.next = a: This makes b (node 2) point to a (node 1), effectively swapping the pair:

pre -> 2 (b) -> 1 (a) -> 3 -> 4 a.next = b.next: Finally, this ensures a (node 1) now points to what b.next was originally pointing to (i.e., node 3), maintaining the connection to the rest of the list:

pre -> 2 (b) -> 1 (a) -> 3 -> 4 This ensures that the part of the list after the swapped nodes (3 -> 4) is preserved.

Final Structure: After the swap, the linked list looks like this:

pre -> 2 (b) -> 1 (a) -> 3 -> 4 The loop will then continue to process the next pair (if any).

Why It Works: In Python, the tuple assignment happens simultaneously, so the pointers are updated all at once, without intermediate values being lost. If you had updated them sequentially, you could have lost part of the list during the process. However, Python's tuple unpacking keeps everything connected correctly.

Upvotes: 0

kriti
kriti

Reputation: 146

You have to preserve starting node of next pair as well as last node of the list reversed so far. I don't code in python so I can provide an algorithm to achieve what you are looking for. You can check following

1. newHead=null
2. previousNode=null
3. while head is not null : // While loop start
      curr = head.next;
      if curr is not null:  // If block
         next= curr.next
         curr.next=head
         head.next=null
      else:
         next=head
                         //If-else block ends here
      
      if prevNode is not null:  // Another if block
         prevNode.next=curr
                                // If block ends here

      prevNode=head
    
      if newNode is null :  // another if block
         newNode=curr
                          // if block ends here
    
      head=next
                        // while loop ends here

4. return newHead         // return head of reversedList

Upvotes: 0

Related Questions