2. Add Two Numbers

문제

Medium

 

Description

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.

 

Examples

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

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

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.

 

Solution : Elementary Math

1. 현재 노드를 (결과값으로 반환할) 더미헤드로 초기화한다
2. carry를 0으로 초기화한다
3. 리스트 2개 모두 end에 도달할 때까지 반복해서 돈다
   
   1. x에 l1의 값을 넣는다. (l1이 마지막 노드라면 0을 넣는다)
   2. y에 l2의 값을 넣는다. (l2가 마지막 노드라면 0을 넣는다)
   3. 합은 x + y + carry이다.
   4. carry를 sum / 10으로 업데이트한다
   5. 새 노드를 생성해서 sum % 10의 값을 넣고 현재 노드의 next로 설정한다. 현재 노드를 앞으로 한 칸 이동한다(새노드가 현재 노드가 된다는 뜻)
   6. l1, 12를 전진시킨다(노드 하나씩 이동)
4. 더미헤드의 next를 반환한다.

 

(english)

1. Initialize current node to dummy head of the returning list.
2. Initialize carry to 0.
3. Loop through lists l1 and l2 until you reach both ends.
   1. Set x to node l1's value. If l1 has reached the end of l1, set to 0.
   2. Set y to node l2's value. If l2 has reached the end of l2, set to 0.
   3. Set sum=x+y+carry.
   4. Update carry=sum/10.
   5. Create a new node with the digit value of (sum  mod 10) and set it to current node's next, then advance current node to next.
   6. Advance both l1 and l2.
4. Return dummy head's next node.

 

Code (Go)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// initialize
	curNode := &ListNode{}
	dummyHead := curNode
	carry := 0

	// loop until reaching the end
	for !(l1 == nil && l2 == nil) {
		x := 0
		if l1 != nil {
			x = l1.Val
			l1 = l1.Next
		}

		y := 0
		if l2 != nil {
			y = l2.Val
			l2 = l2.Next
		}

		sum := x + y + carry
		carry = sum / 10
		curNode.Next = &ListNode{sum % 10, nil}
		curNode = curNode.Next
	}

	if carry > 0 {
		curNode.Next = &ListNode{1, nil}
	}
	return dummyHead.Next
}

 

Complexity Analysis

시간 복잡도 : O(max(m,n))

    m과 n이 l1과 l2의 길이라고 했을 때, 이 알고리즘은 최대 max(m,n)만큼 순회한다.

 

공간 복잡도 : O(max(m,n))

    결과로 반환하는 새 리스트는 최대 max(m,n) +1의 길이를 가진다.

 

(english)

Time complexity: O(max(m,n))

     Assume that m and n represents the length of l1 and l2 respectively, the algorithm above iterates at most max⁡(m,n) times.

Space complexity: O(max(m,n))

    The length of the new list is at most max⁡(m,n)+1.