Question

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

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Algorithm

Create a new LinkedList, and then push the input two linked lists from the beginning to the back, add every two, and add a new node to the back of the new linked list.

In order to prevent the two input linked lists from being empty at the same time, we create a dummy node, and add the new nodes generated by the addition of the two nodes to the dummy node in order.

Since the dummy node itself cannot be changed, a pointer is used cur to point to the last node of the new linked list. Ok, you can start to add the two linked lists.

This problem is good because the lowest bit is at the beginning of the linked list, so you can directly add them in order from low to high while traversing the linked list. The condition of the while loop, as long as one of the two linked lists is not an empty row, since the linked list may be empty, when taking the current node value, judge first, if it is empty then value is 0, otherwise take the node value.

Then add the two node values, and add carry. Then update carry, directly sum/10, and then create a new node with sum%10 as the value, connect it to the back of cur, and then move cur to the next node.

Then update the two nodes, if they exist, point to the next location. After the while loop exits, the highest carry issue needs to be dealt with specially. If carry is 1, then another node with value 1 is created.

Code

public class Add_Two_Numbers {

	public class Solution {
	    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	        if (l1 == null || l2 == null) {
	            return l1 == null ? l2 : l1;
	        }

	        // boolean style, 0 or 1
	        int carry = 0;

	        ListNode dummy = new ListNode(0);
	        ListNode dummyCopy = dummy;

	        while (l1 != null || l2 != null) {
	            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;

	            // append to result list
	            dummy.next = new ListNode(sum % 10);
	            carry = sum >= 10 ? 1 : 0;

	            // move to next node
	            l1 = l1 == null ? null : l1.next;
	            l2 = l2 == null ? null : l2.next;
	            dummy = dummy.next;
	        }

	        // @note: I missed final check
	        if (carry == 1) {
	            dummy.next = new ListNode(carry);
	        }

	        return dummyCopy.next;
	    }
	}

}

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

/**
 * 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) {
        ListNode dummy = new ListNode(0);
        int carry = 0;
        ListNode cur = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            carry = s / 10;
            cur.next = new ListNode(s % 10);
            cur = cur.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return dummy.next;
    }
}

// OJ: https://leetcode.com/problems/add-two-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* addTwoNumbers(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;
    }
};

# 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: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode()
        carry, curr = 0, dummy
        while l1 or l2 or carry:
            s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, val = divmod(s, 10)
            curr.next = ListNode(val)
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

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

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

class Solution(object):
  # maybe standard version
  def _addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    p = dummy = ListNode(-1)
    carry = 0
    while l1 and l2:
      p.next = ListNode(l1.val + l2.val + carry)
      carry = p.next.val // 10
      p.next.val %= 10
      p = p.next
      l1 = l1.next
      l2 = l2.next

    res = l1 or l2
    while res:
      p.next = ListNode(res.val + carry)
      carry = p.next.val // 10
      p.next.val %= 10
      p = p.next
      res = res.next
    if carry:
      p.next = ListNode(1)
    return dummy.next

  # shorter version
  def addTwoNumbers(self, l1, l2):
    p = dummy = ListNode(-1)
    carry = 0
    while l1 or l2 or carry:
      val = (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
      carry = val // 10
      p.next = ListNode(val % 10)
      l1 = l1 and l1.next
      l2 = l2 and l2.next
      p = p.next
    return dummy.next

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    carry := 0
    cur := dummy
    for l1 != nil || l2 != nil || carry != 0 {
        s := carry
        if l1 != nil {
            s += l1.Val
        }
        if l2 != nil {
            s += l2.Val
        }
        carry = s / 10
        cur.Next = &ListNode{s % 10, nil}
        cur = cur.Next
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    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)
 *     }
 * }
 */

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null,
): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    let sum = 0;
    while (sum !== 0 || l1 != null || l2 != null) {
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        sum = Math.floor(sum / 10);
    }
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    const dummy = new ListNode();
    let carry = 0;
    let cur = dummy;
    while (l1 || l2 || carry) {
        const s = (l1?.val || 0) + (l2?.val || 0) + carry;
        carry = Math.floor(s / 10);
        cur.next = new ListNode(s % 10);
        cur = cur.next;
        l1 = l1?.next;
        l2 = l2?.next;
    }
    return dummy.next;
};

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
  dummy = ListNode.new()
  carry = 0
  cur = dummy
  while !l1.nil? || !l2.nil? || carry > 0
      s = (l1.nil? ? 0 : l1.val) + (l2.nil? ? 0 : l2.val) + carry
      carry = s / 10
      cur.next = ListNode.new(s % 10)
      cur = cur.next
      l1 = l1.nil? ? l1 : l1.next
      l2 = l2.nil? ? l2 : l2.next
  end
  dummy.next
end

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        int carry = 0;
        ListNode cur = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            carry = s / 10;
            cur.next = new ListNode(s % 10);
            cur = cur.next;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return dummy.next;
    }
}

import std/[strutils, algorithm]

type
  Node[int] = ref object
    value: int
    next: Node[int]

  SinglyLinkedList[T] = object
    head, tail: Node[T]

proc append[T](list: var SinglyLinkedList[T], data: T = nil): void =
  var node = Node[T](value: data)
  if list.head.isNil:
    list.head = node
    list.tail = node
  else:
    list.tail.next = node
    list.tail = node

proc preview[T](list: SinglyLinkedList[T]): string =
  var s: seq[T]
  var n = list.head
  while not n.isNil:
    s.add n.value
    n = n.next
  result = s.join(" -> ")

proc addTwoNumbers(l1: var SinglyLinkedList, l2: var SinglyLinkedList): SinglyLinkedList[int] =
  var
    aggregate: SinglyLinkedList
    psum: seq[char]
    temp_la, temp_lb: seq[int]

  while not l1.head.isNil:
    temp_la.add(l1.head.value)
    l1.head = l1.head.next

  while not l2.head.isNil:
    temp_lb.add(l2.head.value)
    l2.head = l2.head.next

  psum = reversed($(reversed(temp_la).join("").parseInt() + reversed(temp_lb).join("").parseInt()))
  for i in psum: aggregate.append(($i).parseInt())

  result = aggregate

var list1: SinglyLinkedList[int]
var list2: SinglyLinkedList[int]

for i in @[2, 4, 3]: list1.append(i)
for i in @[5, 6, 4]: list2.append(i)

echo(preview(list1))
echo(preview(list2))
echo(preview(addTwoNumbers(list1, list2)))

// 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 {
    pub fn add_two_numbers(
        mut l1: Option<Box<ListNode>>,
        mut l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode::new(0)));
        let mut cur = &mut dummy;
        let mut sum = 0;
        while l1.is_some() || l2.is_some() || sum != 0 {
            if let Some(node) = l1 {
                sum += node.val;
                l1 = node.next;
            }
            if let Some(node) = l2 {
                sum += node.val;
                l2 = node.next;
            }
            cur.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum % 10)));
            cur = &mut cur.as_mut().unwrap().next;
            sum /= 10;
        }
        dummy.unwrap().next.take()
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var dummy = ListNode.init()
        var carry = 0
        var l1 = l1
        var l2 = l2
        var cur = dummy
        while l1 != nil || l2 != nil || carry != 0 {
            let s = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
            carry = s / 10
            cur.next = ListNode.init(s % 10)
            cur = cur.next!
            l1 = l1?.next
            l2 = l2?.next
        }
        return dummy.next
    }
}

2 - Add Two Numbers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions