Swap every two nodes in linked list

Anusha Yerram 0
Viewed 71

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.)

# Definition for singly-linked list.
 class ListNode(object):
     def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur =head
        while cur and cur.next:
            nxtPair=cur.next.next 
            second=cur.next
            cur.next=nxtPair
            second.next=cur
            cur=second 
            cur=cur.next.next       
        return head 

   input:[1,2,3,4]
   output:
   [1,3]
   expected:
   [2,1,4,3]

I found a solution using dummy linkedlist but without using dummy linkedlist I didn't understand what mistake I made. To have more clarity on this concept can anyone help me with this problem.Here head is not being updated for example , If I have to swap 1,2 to 2,1..head is not being updated to 2,1 instead having only node with 1 as value

swap linked-list python
3 Answers

It doesn't look like you are updating head. After you do your first swap, you need to reassign head. Most likely, your dummy node is properly pointing to the correct "new" head and so it works.

Here is a working implementation without a dummy node.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        new_head = None
        curr = head
        prev = None
        
        if curr and not curr.next:
            return curr
        
        while curr and curr.next:
            next_ = curr.next
            next_next = next_.next
            print(curr.val, next_.val, prev.val if prev else None)
            
            curr.next = next_next
            next_.next = curr
            if prev:
                prev.next = next_

            prev = curr
            curr = curr.next
            
            if not new_head:
                print("setting head", next_.val)
                new_head = next_

        return new_head
Andrew Parmar0

There is something different about the first pair swap as opposed to all pair swaps afterward: the first pair swap does not have a predecessor, but so you only need to update two linkages (and remember to change the head), while future updates require you to go back to the predecessor and update it, and so you need three linkage updates.

So there is some special handling of the first case. You could either give the list a dummy head so that the first swap updates its predecessor just like the rest of the swaps, or you can peel off the first loop like this:

def swapPairs(head):
    if head and head.next:
        # Before: (head=c1) --> c2 --> c3
        #  After: (head=c2) --> c1 --> c3
        c1 = head
        c2 = c1.next
        c3 = c2.next
        head = c2
        c2.next = c1
        c1.next = c3
        cur = c1

        while cur.next and cur.next.next:
            # Before: cur --> c1 --> c2 --> c3
            #  After: cur --> c2 --> c1 --> c3
            c1 = cur.next
            c2 = c1.next
            c3 = c2.next
            cur.next = c2
            c2.next = c1
            c1.next = c3
            cur = c1

    return head

(or you could keep a "prev" variable and add an "if this isn't the first loop..." condition, like in Andrew Parmar's solution)

useroA5M0

You gotta love python, it makes it possible to implement such operation as simply as this:

def swap_pairs(n):
  if n and n.next:
    head = n.next
    head.next, n.next = n, swap_pairs(head.next)
    return head
  return n

There is a lot going on here:

  • no head second argument is needed in the function (provided that is mutates the original list). Also, you can return the head in every recurrence call, and only the first one will be seen back in the original call site.
  • the swap idiom with tuple assignment (a, b = b, a) is one of the most elegant and underrated python features. Note that the order is important: if you had n.next, head.next instead, you could end up with an infinite recursion or something worse.

Here is a simple unit test for it:

class ListNode:
  def __init__(self, val, next=None):
    self.val, self.next = val, next
  def __repr__(self):
    return f"{self.val} {self.next or '.'}"
  @classmethod
  def of(cls, val, *rest):
    return cls(val, cls.of(*rest) if rest else None)

print(swap_pairs(ListNode.of(1, 2, 3, 4)))  # 2 1 4 3 .
print(swap_pairs(ListNode.of(1, 2, 3)))     # 2 1 3 .
print(swap_pairs(ListNode.of(1, 2)))        # 2 1 .
print(swap_pairs(ListNode.of(1)))           # 1 .
Rodrigo Rodrigues0
Related