[leetcode] 24. 两两交换链表中的节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

解题方法

方法一：数组存储

已知链表结点两两交换，那我们只需要提供两个$list$集合，分别按先后顺序存储交换后的结点。遍历链表时以$num$计数（$num$初始为0），每遍历到一个结点，记录当前$num$的奇偶性，当$num$是偶数时，将当前结点添加到$list2$中；若$num$是奇数时，则将当前结点添加到$list1$中。之后，$num++$。数组存储完成之后，我们按照先$list1$的一个结点，再$list2$的一个结点添加到最终链表的尾部。直到数组遍历完成，此时$list1$的第一个结点即为交换后链表的头结点。

java代码

ListNode结构

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

结点交换方法

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    List<ListNode> list1 = new ArrayList<>();
    List<ListNode> list2 = new ArrayList<>();
    int num = 0;
    ListNode curNode = head;
    while (curNode != null) {
        if (num % 2 == 0) {
            list2.add(curNode);
        } else {
            list1.add(curNode);
        }
        num++;
        curNode = curNode.next;
    }
    for (int i = 0; i < list1.size(); i++) {
        ListNode node = list1.get(i);
        node.next = list2.get(i);
        //list1没遍历到尾部
        if (i != list1.size() - 1) {
            //list1后面还有结点
            node.next.next = list1.get(i + 1);
        } else {
            //list2比list1多一个元素
            if (list2.size() > list1.size()) {
                //list2的最后一个元素是最后一个结点
                node.next.next = list2.get(i + 1);
            } else {
                //list1和list2元素一样多，list2最后一个结点的next指针指向null
                node.next.next = null;
            }
        }
    }
    return list1.get(0);
}

复杂度分析

时间复杂度：需要遍历一次链表，再遍历一次$list$数组，所以渐进时间复杂度为$O(N)$，$N$为链表长度。
空间复杂度：$O(N)$。需要用数组存储链表结点。

方法二：递归

我们还可以采用递归的方式构造交换链表。思路是在每次递归中，记$swapPairs$方法中的参数$head$为第一个结点，第二个结点是$head.next$，记为$newHead$，第三个结点是$newHead.next$结点，记$nextHead$结点。我们需要将$newHead$变为第一个结点，并将$newHead.next$指向$head$，然后将$head.next$结点指向$swapPairs(nextHead)$返回的结点，最终返回参数为$newHead$。终止条件是当$head$或者$head.next$为空时，直接返回$head$。

java代码

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

复杂度分析

时间复杂度：需要遍历一次链表，所以渐进时间复杂度为$O(N)$，$N$为链表长度。递归深度为$N/2$，$N$最大为100，深度最大为50，不会栈溢出。
空间复杂度：$O(N)$。空间复杂度主要取决于递归栈占用的空间。

方法三：迭代

为了减少递归栈占用的空间，我们也可以将递归改为迭代的方式。我们记遍历中原链表的第一个结点为$preNode$，$preNode$的$next$结点为第二个结点，记为$node$，第三个结点为$node$的$next$结点，记为$nextPreNode$。每次迭代中，如果$nextPreNode$和$nextPreNode.next$存在，我们需要将$node.next$指向$preNode$，$preNode.next$指向$nextPreNode.next$。再将$preNode$指向$nextPreNode$，$node$指向$nextPreNode.next$，进入下一次迭代。
若迭代中$nextPreNode$或者$nextPreNode.next$不存在，则$node.next$指向$preNode$，$preNode.next$指向$nextPreNode$，然后跳出迭代。

java代码

public ListNode swapPairs2(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = head.next;
    ListNode node = newHead;
    ListNode preNode = head;
    while (true) {
        ListNode nextPreNode = node.next;
        node.next = preNode;
        //nextPreNode后面不再有结点
        if (nextPreNode == null || nextPreNode.next == null) {
            preNode.next = nextPreNode;
            break;
        }
        preNode.next = nextPreNode.next;
        preNode = nextPreNode;
        node = nextPreNode.next;
    }
    return newHead;
}

复杂度分析

时间复杂度：需要遍历一次链表，所以渐进时间复杂度为$O(N)$。
空间复杂度：$O(1)$。只有常数级别的指针存储。

• 个人公众号
  
• 个人小游戏