链表

两两交换链表中的节点

中等#24Java时间 O(n)空间 O(1)

题目要做什么

每两个相邻节点交换位置,返回新的头节点。必须修改节点连接,不能只交换节点值。最后不足两个节点时保留。

题目示例输入head = [1,2,3,4]
题目示例输出[2,1,4,3]

01 为什么这样做

prev 指向待交换两个节点的前驱。先让 first 接上后续链,再让 second 接 first,最后让 prev 接 second;把前驱移到交换后的尾节点。

始终成立的条件

prev 之前的节点已经按对交换,prev.next 是下一对的第一个节点。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode swapPairs(ListNode head) {3        ListNode dummy = new ListNode(0, head), prev = dummy;4        while (prev.next != null && prev.next.next != null) {5            ListNode first = prev.next, second = first.next;6            first.next = second.next;7            second.next = first;8            prev.next = second;9            prev = first;10        }11        return dummy.next;12    }13}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索