LeetCode: Add Two Numbers Solution

Example of using dummy head technique

Dummy head technique in linked list

Use a dummy node to refer back to head

We could also understand this dummy node as a previous node of head

1let dummy = (iter = new ListNode())
2
3// begin iteration
4iter.next = new ListNode(/* calculation for new node */)
5iter = iter.next // new ref for pointer
6// end iteration
7
8return dummy.next

Approach

Use dummy head for later head reference

Iteration will finish when both pointers for 2 lists are null

The rest is handle sum and conditioning when

  • sum is larger or equal than 10
  • two lists are different in length

Remember to check the remainder at last

Implementation

1var addTwoNumbers = function (l1, l2) {
2 let iter1 = l1
3 let iter2 = l2
4 let dummy = (iter = new ListNode())
5 let remainder = 0
6
7 while (iter1 || iter2) {
8 let val1 = iter1 ? iter1.val : 0
9 let val2 = iter2 ? iter2.val : 0
10 let val = val1 + val2 + remainder
11 remainder = 0
12 if (val >= 10) {
13 val -= 10
14 remainder = 1
15 }
16 iter.next = new ListNode(val)
17 iter = iter.next
18 iter1 = iter1 ? iter1.next : iter1
19 iter2 = iter2 ? iter2.next : iter2
20 }
21 if (remainder === 1) {
22 iter.next = new ListNode(1)
23 }
24
25 return dummy.next
26}

Comments

Loading comments...

Tags

leetcode

linked list

math

Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.

Next Post

LeetCode: Flatten a Multilevel Doubly Linked List

Aug 21, 2021

Naming variables is also important

Previous Post

LeetCode: Merge Two Sorted Lists

Aug 19, 2021

(IMO) Not easy as categorized

HoningJS

Search Posts