【LeetCode链表#9】图解：两两交换链表节点

两两交换链表中的节点

力扣题目链接(opens new window)

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

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

思路

这里还是要应用虚拟头节点，不然交换链表头节点的操作会与交换其他节点时不同

交换的过程其实不难理解，但是代码实现过程需要注意很多细节

下面是交换过程的图解

首先，定义一个虚拟头节点

并让当前指针cur指向dummy head【注意：cur一定要在需要操作的两个节点之前】

然后按途中顺序将对应节点的next指好即可

注意：虽然画图我们很好理解，但是在操作过程中有很多细分步骤，如果直接上手写代码会很困惑

例如，当dummy指向节点2（也就是cur.next.next）后，dummy与原来的节点1就断开连接了

此时再想通过cur去寻找到节点1（cur.next）就行不通了，进而节点2也就无法指向节点1，步骤②无法继续进行

与翻转链表时类似，我们需要一个临时节点temp先去保存节点1

让节点2通过指向temp的方式找到节点1

ps：为什么不存节点2？因为步骤①之后节点2就已经是cur.next了，而dummy是不会变的，所以怎么都能找到节点2

当节点2指向temp（储存有cur.next）后，节点2与原来的节点3就断开连接了

同理，我们应该把节点3也用临时节点保存，这里用temp1保存

于是节点2指向节点3的过程就变成了：

temp1是节点3的备份，它后面还是和节点4连着，所以不用担心找不到节点4

至此，节点1与节点2完成了交换，cur移动到cur.next.next（即交换后此处为节点1，是什么节点并不重要，反正待会交换的又不是当前cur指向的节点，而是后两个节点），展开后的结果如下：

链表节点数为奇数时，结束条件：cur.next.next = null

链表节点数为偶数时，结束条件：cur.next = null

代码

思路通过画图可以很好理解，但是代码实现又有很多坑

class Solution {

    public ListNode swapPairs(ListNode head) {

        //定义虚拟头节点

        ListNode dummy = new ListNode(0);

        dummy.next = head;//虚拟头节点指向head

        ListNode cur = dummy;

        //定义临时节点用于保存节点1、3

        ListNode temp;

        ListNode temp1;

        //遍历链表

        //注意这里的结束条件，链表节点数为奇偶情况下是不同的

        //需要先验证cur.next再验证cur.next.next

        //要不然如果是偶数个节点你先验cur.next.next直接就空指针异常了

        while(cur.next != null && cur.next.next != null ){

            //这里下意识肯定就想开始交换了，但如果不先保存节点就会出现空指针异常

            temp = cur.next;

            temp1 = cur.next.next.next;

            cur.next = cur.next.next;//dummy换2

            cur.next.next = temp;//2换1

            cur.next.next.next = temp1;//1换3

            cur = cur.next.next;//移动cur至新的待交换的两个节点前

        }

        //遍历结束，返回dummy的下一个节点即可

        return dummy.next;

    }

}

易错点：

1、创建完dummy后记得指向head

2、交换过程中要以cur为参照点来表示参与交换的节点，不要变，例如1换3时不能写成

`temp.next = temp1;

巴特西

【LeetCode链表#9】图解：两两交换链表节点

两两交换链表中的节点

思路

代码

最新文章

热门文章