LeetCode - 24. Swap Nodes in Pairs

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

Example:

Given <code>1->2->3->4</code>, you should return the list as <code>2->1->4->3</code>.

Note:

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

交换链表中的节点，题目不难，需要细心，有两种解法。

1.递归，逻辑清晰。用临时节点保存交换中的中间节点，以防链表断裂，节点丢失。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode temp = head.next;
        head.next = swapPairs(head.next.next);
        temp.next = head;
        return temp;
    }
}

2.直接循环做，需要一个假的头节点来保存交换之后的头节点，同样需要临时节点保存交换中的中间节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fakeHead = new ListNode(0), pre = fakeHead, temp = null;
        fakeHead.next = head;
        while (pre.next!=null && pre.next.next!=null) {
            temp = pre.next.next;
            pre.next.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
            pre = temp.next;
        }
        return fakeHead.next;
    }
}

在LeetCode上循环比递归耗时减少1ms