Learning to Swap Nodes in Pairs

Question

I am learning to swap nodes. The problem comes from Leetcode:

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Now, obviously my attempt is NOT working and I am confused(as usual) why temp in the code gets updated.

head = [1,2,3,4,5,6]

def swapPairs(self):
  temp=self
  print("orig %s", (temp))
  for x in range(len(self)):
    if x%2!=0:
      print("temp odd before %s", (temp))
      self[x]=temp[x-1]
      print("temp odd after %s", (temp))
    else:
      print("temp even before %s", (temp))
      self[x]=temp[x+1]
      print("temp even after %s", (temp))
  return self

I see that when I am printing temp the values of it are getting updated. But it is on the right side of equation.

How can that happen ?

The Second problem is the actual problem of swapping node.

The odd elements are switched with the previous even element.

Please advise.

Thank You

user_17769815 · Answer

To answer your immediate question,

temp=self

points temp and self to the same location in memory. Modifications to the list referenced by self will be reflected in temp, and vice versa. The solution is to create a copy of the list, either by doing

temp[:]=self

or

temp=list(self)

However, I'm going to include a solution to the problem proper, because even if you resolve this issue, you'll need to figure out how to perform the operations on a linked list, which isn't necessarily a trivial task. Essentially, for each pair of nodes you need to keep track of:

the first node in the pair
the second node in the pair
the node previous to the first node in the pair, so that its next field can be appropriately set.

We make one pass through the list, modifying the pointers as desired:

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        has_head_changed = False
        current_node = head
        previous = None
        while current_node and current_node.next:
            next_node = current_node.next
            current_node.next = current_node.next.next
            next_node.next = current_node
            
            if previous:
                previous.next = next_node
                
            if not has_head_changed:
                head = next_node
                has_head_changed = True
            
            previous = current_node
            current_node = current_node.next
                        
        return head

Learning to Swap Nodes in Pairs

1 Answers