LeetCode 23 – Swap Nodes in Pairs

Solution to LeetCode Swap Nodes in Pairs problem.

First, I think this is not a good interview questions, as it doesn’t really test any algorithmic thinking, but on the other hand is extremely prone to any off-by-one errors which in the case of working with linked lists manifest themselves as either null dereferences, or subtly incorrect code. This is the exact question I got for an interview with Mixpanel. Coupled with the fact I was required to do it in Python even though my Python knowledge was very limited, I must have made the interviewer think I’m intellectually challenged when it comes to programming. Needless to say, I didn’t get the position. So, Tim Trefren, in case you need to swap nodes in pairs in a linked list again, here is some working Java code. It is absolutely nothing fancy, but difficult to get correct under a situation where someone is watching your every keystroke.

public ListNode swapPairs(ListNode head) {
  if(head == null || head.next == null) return head; // one element only
  ListNode newHead = head.next;
  ListNode tmp = null;
  ListNode prev = null;

  while(head != null){
    if(head.next != null){
      tmp = head.next.next;
      head.next.next = head;
      if(prev != null) prev.next = head.next;
      head.next = tmp;
      prev = head;
      head = tmp;                
    } else{
      prev.next = head;
      head = null;
    }
  }
  return newHead;
}