Java Fast Slow Pointer Solution O(n) time O(1) space with explanation, no reversing output


  • 0
    G
    1. Calculate length of two linked lists
    2. Fast pointer is the current digit being added
    3. Slow pointer remember the latest non-9 digit
    4. If a sum > 10 appears, slow pointer value is incremented, and all the values between slow and fast pointers are cleared to 0 (because they were all 9)
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            int len1 = getLength(l1), len2 = getLength(l2);
            if (len1 < len2) {
                ListNode tmpN = l1;  int tmpL = len1;
                l1 = l2;             len1 = len2;
                l2 = tmpN;           len2 = tmpL;
            }
            ListNode dummy = new ListNode(0), cur1 = l1, cur2 = l2, resL = dummy, resR = dummy, prevR = resR;
            for (int i = 0; i < len1; i++) {
                int sum = cur1.val + ((i < len1 - len2) ? 0 : cur2.val);
                if (sum >= 10) {
                    resL.val++;
                    while (resL != resR) {
                        resL = resL.next;
                        resL.val = 0;
                    }
                }
                resR.next = new ListNode(sum % 10);
                resR = resR.next;
                resL = (sum == 9) ? resL : resR;
                cur1 = cur1.next;
                cur2 = (i < len1 - len2) ? cur2 : cur2.next;
            }
            return (dummy.val == 0) ? dummy.next : dummy;
        }
        public int getLength(ListNode head) {
            ListNode dummy = new ListNode(0), slow = dummy, fast = dummy;
            dummy.next = head;
            int len = 0;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                len += 2;
            }
            return (fast == null) ? len - 1 : len;
        }
    }
    

Log in to reply
 

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