[leetcode javascript解题]Swap Nodes in Pairs

小鱼儿 2022-07-13 03:18 121阅读 0赞

leetcode 24题 “ Swap Nodes in Pairs”描述如下：

> Given a linked list, swap every two adjacent nodes and return its head.  
> For example,  
> Given `1->2->3->4`, you should return the list as \`2->1->4->3.

这道题乍一看不难好像就是两两交换位置，改变两个list的next的指向，然后再移动head指针到下下个链表。最初我也是很快这样做的。  
但结果不对，果然单凭脑袋空间想象就容易漏一些细节。于是认真在纸上画出来才发现，除了改变head和head.next的next指向外，在本次操作还需要改变上一次循环最初head指向的节点的next指针。  
用图形表示就是第一步从`1->2->3->4`变成`2->1->3->4`，第二步变成`2->1->3<-4` 因为实际上循环中没有操作值为1的节点的next指针，它还是指向值为3的节点。显然结果不对。  
所以需要一个额外的指针在每次循环结束前也就是head指向head.next前，指向head的原位置。然后在下次循环时，就能使上一次的head指向下次的head.next。而第一次进行循环时，不存在上一个head，所以需要new一个节点。  
结果的话如果链表里的长度小于2，直接返回，如果大于等于2，返回最初的head.next就可以了。原理很简单。

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {ListNode} */
    var swapPairs = function(head) {
        if (!head || !head.next) {
            return head;
        }
        var curr = new ListNode(0),
            result = head.next;
        while (head && head.next) {
            var temp = head.next;
            curr.next = temp.next;
            temp.next = head;
            head.next = curr.next;
            curr.next = temp;//改变上一个head的next指向
            curr = head;//指向当前head所处节点
            head = head.next;
        }
        return result;
    };

感觉自己语言描述的比较乱，代码比较清晰吧，画个图就可以理解，如果有什么问题欢迎交流。