Question

Formatted question description: https://leetcode.ca/all/445.html

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Algorithm

This question is an extension of the previous Add Two Numbers. We can see that the highest position of this question is at the top of the linked list. If we flip the linked list, it will be the same as the previous question.

Here we look at some unmodified ones. The method of linked list order. Since addition needs to start from the lowest bit, and the lowest bit is at the end of the linked list, the linked list can only be traversed from the front to the back, and the previous elements cannot be retrieved.

What should I do? We can use the stack to store all the elements, and then use the last-in-first-out feature of the stack to fetch numbers from back to front.

We first traverse the two linked lists and push all the numbers into the two stacks s1 and s2. We create a res node with a value of 0, and then start the loop. If the stack is not empty, add the top number of the stack to sum, then assign the res node value to sum%10, and then create a new carry node head, and assign it to sum /10, if there is no carry, then it is 0, and then we connect res after the head, and point res to head, so that after the loop exits, we only need to see if the value of res is 0, if it is 0, return res->next, not 0 Just return res, see the code as follows:

Code

C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int sum = 0;
        ListNode *res = new ListNode(0);
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {sum += s1.top(); s1.pop();}
            if (!s2.empty()) {sum += s2.top(); s2.pop();}
            res->val = sum % 10;
            ListNode *head = new ListNode(sum / 10);
            head->next = res;
            res = head;
            sum /= 10;
        }
        return res->val == 0 ? res->next : res;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<ListNode>();
        Stack<ListNode> stack2 = new Stack<ListNode>();
        ListNode temp1 = l1, temp2 = l2;
        while (temp1 != null) {
            stack1.push(temp1);
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            stack2.push(temp2);
            temp2 = temp2.next;
        }
        Stack<ListNode> stackSum = new Stack<ListNode>();
        int carry = 0;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            ListNode node1 = stack1.pop(), node2 = stack2.pop();
            int curVal = carry + node1.val + node2.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (!stack1.isEmpty()) {
            ListNode node1 = stack1.pop();
            int curVal = carry + node1.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (!stack2.isEmpty()) {
            ListNode node2 = stack2.pop();
            int curVal = carry + node2.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (carry > 0) {
            int curVal = carry % 10;
            carry /= 10;
            ListNode curNode = new ListNode(curVal);
            if (!stackSum.isEmpty())
                curNode.next = stackSum.peek();
            stackSum.push(curNode);
        }
        return stackSum.peek();
    }
}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();
        for (; l1 != null; l1 = l1.next) {
            s1.push(l1.val);
        }
        for (; l2 != null; l2 = l2.next) {
            s2.push(l2.val);
        }
        int carry = 0;
        ListNode dummy = new ListNode();
        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
            ListNode node = new ListNode(carry % 10, dummy.next);
            dummy.next = node;
            carry /= 10;
        }
        return dummy.next;
    }
}

// OJ: https://leetcode.com/problems/add-two-numbers-ii/
// Time: O(N)
// Space: O(1)
class Solution {
    ListNode *reverse(ListNode *h) {
        ListNode dummy;
        while (h) {
            auto p = h;
            h = h->next;
            p->next = dummy.next;
            dummy.next = p;
        }
        return dummy.next;
    }
    ListNode* add(ListNode* a, ListNode* b) {
        int carry = 0;
        ListNode dummy, *tail = &dummy;
        while (a || b || carry) {
            if (a) {
                carry += a->val;
                a = a->next;
            }
            if (b) {
                carry += b->val;
                b = b->next;
            }
            tail->next = new ListNode(carry % 10);
            tail = tail->next;
            carry /= 10;
        }
        return dummy.next;
    }
public:
    ListNode* addTwoNumbers(ListNode* a, ListNode* b) {
        a = reverse(a);
        b = reverse(b);
        return reverse(add(a, b));
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        carry, dummy = 0, ListNode()
        while s1 or s2 or carry:
            carry += (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop())
            carry, val = divmod(carry, 10)
            node = ListNode(val, dummy.next)
            dummy.next = node
        return dummy.next

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """

    def r(root):
      pre = None
      cur = root
      while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
      return pre

    p = dummy = ListNode(-1)
    p1, p2 = r(l1), r(l2)
    pre = None
    carry = 0
    while p1 and p2:
      p.next = ListNode(p1.val + p2.val + carry)
      carry = 1 if p.next.val > 9 else 0
      p.next.val = p.next.val % 10
      p1 = p1.next
      p2 = p2.next
      p = p.next
    pp = p1 or p2
    while pp:
      p.next = ListNode(pp.val + carry)
      carry = 1 if p.next.val > 9 else 0
      p.next.val = p.next.val % 10
      pp = pp.next
      p = p.next
    head = r(dummy.next)
    if carry:
      n = ListNode(1)
      n.next = head
      head = n
    return head

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	s1, s2 := arraystack.New(), arraystack.New()
	for l1 != nil {
		s1.Push(l1.Val)
		l1 = l1.Next
	}
	for l2 != nil {
		s2.Push(l2.Val)
		l2 = l2.Next
	}
	carry, dummy := 0, new(ListNode)
	for !s1.Empty() || !s2.Empty() || carry > 0 {
		v, ok := s1.Pop()
		if ok {
			carry += v.(int)
		}
		v, ok = s2.Pop()
		if ok {
			carry += v.(int)
		}
		node := &ListNode{Val: carry % 10, Next: dummy.Next}
		dummy.Next = node
		carry /= 10
	}
	return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

const createStack = (head: ListNode | null) => {
    const res = [];
    while (head != null) {
        res.push(head.val);
        head = head.next;
    }
    return res;
};

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null,
): ListNode | null {
    const stack1 = createStack(l1);
    const stack2 = createStack(l2);
    const dummy = new ListNode();
    let sum = 0;
    while (stack1.length !== 0 || stack2.length !== 0 || sum !== 0) {
        sum += (stack1.pop() ?? 0) + (stack2.pop() ?? 0);
        dummy.next = new ListNode(sum % 10, dummy.next);
        sum = Math.floor(sum / 10);
    }
    return dummy.next;
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    fn create_stack(mut head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut res = vec![];
        while let Some(node) = head {
            res.push(node.val);
            head = node.next;
        }
        res
    }

    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut stack1 = Self::create_stack(l1);
        let mut stack2 = Self::create_stack(l2);

        let mut dummy = Box::new(ListNode::new(0));
        let mut sum = 0;
        while !stack1.is_empty() || !stack2.is_empty() || sum != 0 {
            if let Some(val) = stack1.pop() {
                sum += val;
            }
            if let Some(val) = stack2.pop() {
                sum += val;
            }
            dummy.next = Some(Box::new(ListNode {
                val: sum % 10,
                next: dummy.next.take(),
            }));
            sum /= 10;
        }
        dummy.next.take()
    }
}

445 - Add Two Numbers II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions