Given a linked list, swap every two adjacent nodes and return its head.

For example, given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 Definition for singly-linked list.
 
 public class Node {
   int val;
   Node next;
   Node(int x) { val = x; }
 }
 */

public class Solution {
  public Node swapPairs(Node head) {

  }
}

This problem is selected from LeetCode.

Solution

Traverse the linked list. Setup a variable pos to track the position of the current node. If it’s an even node, modify
its next pointer to point to the previous node. If it’s an odd node, modify its next to point to the node 3 nodes after. By this method we could
achive swapping the nodes in pairs.

Be careful to some special cases when the node is an odd node. If the next node is null, this node is the last node in the list and we
don’t need to do anything to it. If the next next node is null, then after the swap, the node will be the last node in the list so make
the next point to null. If the next next next node is null, then make the next node point to the next next node which is the last node in the
list.

public class Solution {
  public Node swapPairs(Node head) {
    if(head==null || head.next==null) 
      return head;
    
    int pos = 1;
    Node prevNode = null;
    Node current = head;
    head = head.next;
    
    while(current !=null) {
      Node temp = current.next;
      if(pos%2!=0) {
        // if it's an odd node
        
        if(current.next==null) 
          //nothing to do
          ;
        else if(current.next.next==null) 
          current.next = null;
        else if(current.next.next.next==null)
          current.next = current.next.next;
        else 
          current.next = current.next.next.next;
        
        prevNode = current;
        
      } else {
        // if it's an even node
        
        current.next = prevNode;
      }
      
      current = temp;
      pos ++;
    }
    
    return head;
  }
}

RelatedPost