Swap Nodes in Pairs(0024/Medium)

LintCode Source

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

Java代码

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;
}

Golang code

type ListNode struct {
    Val  int
    Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := head.Next
    head.Next = swapPairs(newHead.Next)
    newHead.Next = head

    return newHead
}

References

1 Solution from http://rafal.io/