Commented iterative JavaScript solution (accepted)


  • 1
    N
    // https://leetcode.com/problems/reverse-linked-list-ii/
    
    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    
    /**
     * @param {ListNode} head
     * @param {number} m
     * @param {number} n
     * @return {ListNode}
     */
    var reverseBetween = function(head, m, n) {
        // First check that head is valid
        if (head == null) {
            return;
        }
    
        // save the head in case we need it later
        var orig_head = head;
    
        // Then make sure m <= n
        if (!(m <= n)) {
            var temp = m;
            m = n;
            n = temp;
        }
    
        // Next find the nodes at m and n
        var count = 1;
        var current = head;
        var prev = null;
    
        while (current != null && count < m) {
            prev = current;
            current = current.next;
            count += 1;
        }
    
        // sometimes the list may be too short
        // then, we just exit quickly
        if (current == null) {
            return;
        }
    
        // At this point, current is the mth node
        var m_node = current;
        var m_node_prev = prev;
        var n_node = null;
        var n_node_prev = null;
    
        count = 0;
        while (current != null && count < n-m) {
            prev = current;
            current = current.next;
            count += 1;
        }
    
        // ran out again
        if (current == null) {
            return;
        }
    
        n_node = current;
        n_node_prev = prev;
    
        // Begin the reversing procedure
        // First, update the next pointer of m_node
        var orig_m_node_next = m_node.next;
        m_node.next = n_node.next;
        
        if (m_node_prev == null) {
            // we have a new head which is the n_node itself
            head = n_node;
        } else {
            // Remove the connection between m's previous to m
            // and set it to the new head of the reversed part
            m_node_prev.next = n_node;
        }
        
        // Now n_node.next and m_node.next point to the same object
        // (the object could be null, but that's fine too)
    
        current = m_node;
        var next = orig_m_node_next;
        while (current !== n_node) {
            next_next = next.next;
            next.next = current;
            
            current = next;
            next = next_next;
        }
        
        return head;
    };

Log in to reply
 

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