24. Swap Nodes in Pairs

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

先建立一个哨兵节点，next指向head。
交换时同时传入前一个节点pre和当前节点root。
当当前节点非null且下一个节点非null，则可以交换两个节点。
首先保存当前节点的下一个节点next和下一个节点的下一个节点last。

• 1.将pre指向next。
• 2.将next指向root。
• 3.将root指向last。
• 4.处理下一组节点，root作为pre，root.next作为root递归。
  最后返回哨兵节点的next。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        swap(dummy, head);
        return dummy.next;
    }
    
    private void swap(ListNode pre, ListNode root){
        if(root == null || root.next == null){
            return;
        }
        else if(root != null && root.next != null){
            
            ListNode last = root.next.next;
            ListNode next = root.next;
            pre.next = next;
            next.next = root;
            root.next = last;
        }
        swap(root, root.next);
    }
}