JavaScript using original reverseList()


  • 0

    This isn't so pretty compared to the single-pass top solutions posted, but I'll share my strategy using the first Reverse Linked List solution:

    function reverseList(head) {
        if (!head) return null;
        let currNode = head;
        let prevNode = null;
        let nextNode = null;
        while (currNode) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }
        return prevNode;
    }
    

    If we could only apply this to a sublist, we could save some effort... but not really:

    var reverseBetween = function(head, m, n) {
        let dummy = new ListNode();
        dummy.next = head;
        let leftTail = dummy;
        let rightHead = head.next;
        for (let i = 1; i < n; i++) {
            if (i < m) leftTail = leftTail.next;
            rightHead = rightHead.next;
        }
        leftTail.next = reverseList(leftTail.next, n - m + 1);
        while (true) {
            if (!leftTail.next) {
                leftTail.next = rightHead;
                break;
            }
            leftTail = leftTail.next;
        }
        return dummy.next;
    };
    
    function reverseList(head, k = Infinity) {
        if (!head) return null;
        let currNode = head;
        let prevNode = null;
        let nextNode = null;
        while (currNode && --k > -1) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }
        return prevNode;
    }
    

    We end up traversing 2n - m additional nodes compared to just n. (We could shave off m of these by starting rightHead at leftTail but who's counting.)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.