题目

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

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

示例:

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

题解

思路1

递归

时间复杂度: O(N)- 空间复杂度: O(1)

public ListNode swapPairs(ListNode head) {
    ListNode pre = new ListNode(-1);
    return swap(pre,head);
}

/**
 * 递归交换两个节点
 * @return 交换后的头节点
 */
private ListNode swap(ListNode pre,ListNode head){
    if(head == null || head.next == null)
        return head;

    pre = head.next;
    head.next = swap(pre,pre.next);
    pre.next = head;

    return pre;
}