题解 | #两两交换链表的节点#

两两交换链表的节点

http://www.nowcoder.com/practice/71f95c23810349f782a1aa6c9bd714b4

题意整理

给定一个链表，要求两两交换相邻节点。

方法一（递归）

1.思路整理

递归终止条件：只有一个节点，或没有节点了，递归终止。
递归如何传递：通过递归可以得到从当前节点的下下个节点断开之后的链表。比如1-2-3-4中的3-4部分。然后将当前节点的下一个节点，指向这个断开之后的链表，同时记录当前节点的下一个节点作为当前层的头节点newHead，并将head指向断开之后的链表，newHead指向head。
递归的返回值：返回当前层头节点newHead。

2.代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode swapLinkedPair (ListNode head) {
        //递归终止条件
        if (head==null || head.next==null) return head;
        //每次向前递推2个节点，并且与下一级层递归的头节点相连（2指向4）
        head.next.next=swapLinkedPair(head.next.next);
        //当前层的头节点
        ListNode newHead = head.next;
        //当前节点指向当前头指向的节点（1指向4）
        head.next=newHead.next;
        //当前头指向当前节点（2指向1）
        newHead.next=head;
        return newHead;
    }
}

3.复杂度分析

时间复杂度：链表长度是偶数时，需要交换链表中所有的节点，链表长度是奇数，除了最后一个节点，其它节点均需交换，所以时间复杂度为 $O (n)$ 。
空间复杂度：需要额外大小为 $n / 2$ 的递归栈，所以空间复杂度是 $O (n)$ 。

方法二（迭代）

1.思路整理

新建一个虚节点dummy，初始化pre指向dummy，cur指向head。
遍历整个链表，每次保留当前节点下个、下下个节点，然后pre指向cur指向的节点，next指向cur，cur指向之前保留的下下个节点。pre、cur后移两步。
遍历完成后，返回dummy指向的节点即为新的头节点。

图解展示： alt

2.代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode swapLinkedPair (ListNode head) {
        if(head.next==null) return head;
        //虚节点
        ListNode dummy=new ListNode(0);
        //初始化pre指向dummy，cur指向head
        ListNode pre=dummy;
        ListNode cur=head;
        while(cur!=null&&cur.next!=null){
            //保留下下个节点
            ListNode nextnext=cur.next.next;
            //保留下个节点
            ListNode next=cur.next;
            //pre指向cur指向的节点
            pre.next=cur.next;
            //next指向cur
            next.next=cur;
            //cur指向之前保留的下下个节点
            cur.next=nextnext;
            //pre、cur后移两步
            pre=cur;
            cur=nextnext;
        }
        return dummy.next;
    }
}