哪个网站可以学做馒头,公众号关注推广,郑州一核酸点推vip服务 年费320元,那个网站做h5好题目描述
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
示例 1#xff1a; 输入#xff1a; head [1,2,3,4]
输出#…题目描述
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入 head [1,2,3,4]
输出 [2,1,4,3]示例 2
输入 head []
输出 []示例 3
输入 head [1]
输出 [1]提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
分析解答
这道题和链表的逆置并不同。它需要每两个节点和他们后面的下一个也就是第三个节点发生关系(指向)所以可以考虑引入一个虚拟头节点进行操作。
所以现在就成了 dummyHeadcurcur.next 这三个节点的指向不断改变。但此时又有了另一个难点操作的先后顺序。
先以 1 - 2 - 3 为例操作过后为 2 - 1 - 3而 cur 先指向 1然后指向了 2之后还会指向 1此时的 1 是指第一次操作 cur 完成后的后两位。 下图来自代码随想录的题解 现在顺序问题总算说完了下一个难点是节点会丢失这里我使用了 temp 和 temp1 来保存节点以避免这个问题。实际上这里的 dummyHead 也只是为了保存头节点防止丢失。
最后就是考虑边界了cur.next ! null cur.next.next ! null 想必这个在上面问题的衬托下已经变得非常简单了。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
function ListNode(val, next) {this.val (val undefined ? 0 : val)this.next (next undefined ? null : next)
}/*** param {ListNode} head* return {ListNode}*/
var swapPairs function (head) {if (head null || head.next null) return headlet dummyHead new ListNode(0, head)let cur dummyHeadwhile (cur.next ! null cur.next.next ! null) {let temp cur.nextlet temp1 cur.next.next.nextcur.next cur.next.nextcur.next.next temptemp.next temp1cur cur.next.next}return dummyHead.next
};思路拓展