# 24 Swap Node in Pairs

把Linked List裡面的node一對一對的交換

1->2->3->4

2->1->4->3

Concept:

先create一個newHead和要在LinkedList上跑的指針cur和prev。

每讀到一個Node就要記錄他的下下一個，

然後把要交換的兩個Node交換過來，再把這兩個node跟prev和下下一個node接好。

Pseudocode:

create a ListNode newHead = 0
create a ListNode prev = newHead
while cur !=null
    if cur.next!=null
        ListNode tmp = cur.next.next;
        ListNode next = cur.next;//2
        next.next = cur; 
        cur.next = tmp; //2->1->3
        prev.next = next;//*->2->1->3
        prev = cur;
        cur = tmp;
    else
        prev = cur;
        cur = cur.next;
return newHead.next;

Test:
*->2->1->3
1->2->3

Code:

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

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