Java Iterative Solution w/ comments(Top 80% Runtime)


  • 0
    M
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // need 2 pointers to track the end of each list
            ListNode end1 = l1;
            ListNode end2 = l2;
            
            // headPointers
            ListNode l1HeadPointer = new ListNode(0);
            l1HeadPointer.next = l1;
            
            ListNode l2HeadPointer = new ListNode(0);
            l2HeadPointer.next = l2;
            
            // new list for number
            ListNode newNum = new ListNode(0);
            ListNode newNumHead = newNum;
            
            
            // traverse to end of both lists
            while(end1.next != null) end1 = end1.next;
            while(end2.next != null) end2 = end2.next;
            
            // need 2 pointers to traverse to node previous to end pointers so it can move backwards
            ListNode node1 = l1HeadPointer;
            ListNode node2 = l2HeadPointer;
            
            // keep track of carry
            int carry = 0;
            
            //careful that you don't leave out the first numbers, will have to do calculations last or iterations first to compensate
            while(end1 != l1HeadPointer || end2 != l2HeadPointer || carry > 0) {
                // check if end nodes are at the front of the list
                int val1 = (end1 == l1HeadPointer) ? 0 : end1.val;
                int val2 = (end2 == l2HeadPointer) ? 0 : end2.val;
                
                // update values
                newNum.next = new ListNode((val1 + val2 + carry) % 10);
                newNum = newNum.next;
                
                carry = (val1 + val2 + carry) / 10;
                
                // move the end nodes back one
                while(node1.next != end1 && node1 != end1) node1 = node1.next;
                while(node2.next != end2 && node2 != end2) node2 = node2.next;
                end1 = node1;
                end2 = node2;
                
                // reset dummy nodes
                node1 = l1HeadPointer;
                node2 = l2HeadPointer;
            }
            
            // set the new number head
            newNumHead = newNumHead.next;
            
            // reverse the number
            ListNode node = newNumHead;
            ListNode end = newNumHead; 
            
            // set the end to the end of the list
            while(end.next != null) end = end.next;
            
            ListNode head = end;
            
            while(end != newNumHead) {
                // move node to prev end
                while(node.next != end) node = node.next;
                
                // reverse the pointer
                end.next = node;
                // move end back one node
                end = node;
                // reset the dummy pointer
                node = newNumHead;
            }
            
            // signify the end of the list
            end.next = null;
            
            
            return head;
        }
    }
    

Log in to reply
 

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