Swap Nodes in Pairs(交换节点)

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.

两两交换节点。

1、使用递归，简单，空间不是固定的O(n)。

 public ListNode swapPairs(ListNode head) {

        if(head == null||head.next==null) return head;

        //递归，但是空间O(n)

        ListNode node=head.next;

        head.next=swapPairs(head.next.next);

        node.next=head;

        return node;

}

2、直接遍历修改。。两个一组操作。因为头结点也会变，所以需要额外添加头结点。

 //非递归

        ListNode dummy=new ListNode(0);

        dummy.next=head;

        ListNode current=dummy;

        //最后如果只剩一个节点，不用交换，本身就在current上所以不作处理

        while(current.next!=null&&current.next.next!=null){

            ListNode first=current.next;

            ListNode second=current.next.next;

            first.next=second.next;

            current.next=second;

            current.next.next=first;

            current=current.next.next;

        }

        return dummy.next;