【hot100】跟着小王一起刷leetcode -- 24. 两两交换链表中的节点

小王不头秃

发布于 2024-06-19 17:42:48

1210

发布于 2024-06-19 17:42:48

文章被收录于专栏：后端/图像融合/机器学习/爬虫后端/图像融合/机器学习/爬虫

24. 两两交换链表中的节点

题目解读

简单来说，就是将链表的节点两个划分为一组，例如[1,2]一组，[3,4]一组，然后交换组内节点的顺序即可。

那么怎么交换呢，这里我们要注意几个点

首先，如何交换两个节点
交换结束之后，在后面节点的next需要继承前面节点原来的next

思路

首先，怎么交换两个节点，我们先从图示看下流程

这里的A，B就是组内的节点，pre是A前面的节点，方便我们进行更换位置时使用，C代表B原来指向的节点

整个流程如下

首先，pre.next更换为指向B。这时候可能有小伙伴说了，更换之后A的引用不就丢失了吗，所以我们要用iter指向A，这样就没有顾忌了。
然后，我们要把A插到B后面，但是有一个问题。上面我们提到，要把A的next改为C，如果直接把A插到B后面，C的引用不就丢失了。因此，我们首先将A.next改为C，然后再把A插到B后面。

这样我们就完成了交换。

但需要注意的是，我们需要更新pre，以方便下一次的交换，因此直接将pre=iter即可。

最后别忘记移动iter到下一组，直接iter=iter.next，因为现在iter指向的A已经是这个组内的第二个节点了。

实现代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode iter = head;
        ListNode tmp = null;
        ListNode pre = new ListNode();
        ListNode start = head;
        while (iter != null && iter.next != null) {
           // 记录一下最终链表的第一个节点
            if (start == head)
                start = head.next;
           // 节点交换  start
            pre.next = iter.next;
            iter.next = pre.next.next;
            pre.next.next = iter;
            // 节点交换  end
            // 更新pre，方便后续的交换
            pre = iter;
            // 移动下标
            iter = iter.next;
        }

        return start;
    }
}