[leetcode]143. Reorder List -- JavaScript 代码

川长思鸟来 2022-09-25 09:27 2阅读 0赞

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */
    var reorderList = function(head) {
        if(head===null || head.next===null){
            return;
        }
        var top = head;
        var mid = getMid(head);
        var reversedlist = reverseList(mid);
        mergeList(top,reversedlist);
    
    
        function reverseList(firstNode){ // 1->2->3->4->5
            if(firstNode===null || firstNode.next===null){
                return firstNode;
            }
            var node1 = firstNode;
            var node2 = firstNode.next;
            node1.next = null;
            while(node2.next!==null){
                var tmp = node2.next;
                node2.next = node1;
                node1 = node2;
                node2 = tmp;
            }
            node2.next = node1;
            return node2;// the first node of the reversed list
        }
        function mergeList(l1,l2){
       // 1->2->3
            if(l1===null){        // 4->5->6
                return l2;
            }
            if(l2===null){
                return l1;
            }
            while(l1!==null && l2!==null){
                tmp = l1.next;
                l1.next = l2;
                l2 = l2.next;
                l1.next.next = tmp;
                l1 = tmp;
            }
        }
        function getMid(first){ // 快慢指针获得中间点
            var fast = first.next;
            var slow = first.next;
            var prev = first;
            while(true)
            {
                if(fast !== null)
                    fast = fast.next;
                else
                    break;
                if(fast !== null)
                    fast = fast.next;
                else
                    break;
                prev = slow;
                slow = slow.next;
            }
            prev.next = null;  // cut
            return slow;
        }
    };

解题思路分为三部分：

1、function getMid：找到中间节点，将链表一分为二。  
2、function reverseList：将第二个链表倒置。  
3、function mergeList：将两个链表合并。

题目整体略微复杂，但是分开3个小问题，每个都比较好解决。