Easy O(n) Java Solution with reversing linked lists


  • 0
    Y
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode pre1 = null;
            ListNode pre2 = null;
            while (l1 != null) {
                ListNode curr = l1.next;
                l1.next = pre1;
                pre1 = l1;
                l1 = curr;
            }
            while (l2 != null) {
                ListNode curr = l2.next;
                l2.next = pre2;
                pre2 = l2;
                l2 = curr;
            }
            ListNode head1 = pre1;
            ListNode head2 = pre2;
            ListNode dummy = new ListNode(-1);
            ListNode pre = dummy;
            int sum = 0;
            while (head1 != null || head2 != null) {
                sum /= 10;
                if (head1 != null) {
                    sum += head1.val;
                    head1 = head1.next;
                }
                if (head2 != null) {
                    sum += head2.val;
                    head2 = head2.next;
                }
                dummy.next = new ListNode(sum % 10);
                dummy = dummy.next;
            }
            if (sum / 10 > 0) {
                dummy.next = new ListNode(sum / 10);
            }
            ListNode previous = null;
            ListNode head = pre.next;
            while (head != null) {
                ListNode curr = head.next;
                head.next = previous;
                previous = head;
                head = curr;
            }
            return previous;
        }
    }
    

Log in to reply
 

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