Java in place one pass


  • 0
    A
        public ListNode reverseBetween(ListNode head, int m, int n) {
        
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode prev = null;
        ListNode start = null;
        ListNode node = head;
        
        // find the part to reverse
        for (int i=1; i<n+1; i++) {
           if (i == m) {
               start = node;
               break;
           }
           prev = node;
           node = node.next;
        }
        
        // Reverse the part
        ListNode reversedPart = reverseUntil(start, n - m);
        
        // Re-attach the reversed part to the list
        if (prev != null) {
            prev.next = reversedPart;
        } else {
            head = reversedPart;
        }
        
        return head;
    }
    
    public ListNode reverseUntil(ListNode node, int size) {
        ListNode last = null;
        ListNode prev = null;
        ListNode current = node;
        ListNode next = null;
        int i = 0;
        while (i <= size) {
            next = current.next;
            current.next = prev;
            if (prev == null) last = current;
            prev = current;
            current = next;
            i++;
        }
        last.next = current;
        return prev;
    }

Log in to reply
 

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