题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：
给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

解一

由题目可知，每两个节点作为一对进行交换，然后进行下一对的交换。首先编写一个交换节点的函数，然后对原链表进行遍历的过程中，不断调用该函数。原链表的前进速度为2。这道题的难点在于，要创建一个哑节点，然后对后一个节点进行调用函数。

public ListNode swapPairs(ListNode head) {
        if (head == null)
            return null;
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode cur = dummyNode;
        while (cur.next != null && cur.next.next != null) {
            cur.next = swap(cur.next);
            cur = cur.next.next;
        }
        return dummyNode.next;
    }

    private ListNode swap(ListNode cur) {
        ListNode temp = cur.next;
        cur.next = temp.next;
        temp.next = cur;
        return temp;
    }

解二

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null)
        return head;

    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre2 = dummy;
    ListNode pre = head;
    ListNode cur = pre.next;

    while (pre != null && pre.next != null) {
        cur = pre.next;
        pre.next = cur.next;
        cur.next = pre;
        pre2.next = cur;

        pre2 = pre;
        pre = pre.next;
    }

    return dummy.next;
}

递归方法

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

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

    return next;
}