Add Two Numbers Represented as Linked List in DSA Go - Execution Trace

Concept Flow - Add Two Numbers Represented as Linked List

Start with two linked lists

↓

Initialize carry = 0 and dummy head

↓

Traverse both lists simultaneously

↓

Sum current digits + carry

↓

Create new node with sum % 10

↓

Update carry = sum / 10

↓

Move to next nodes in both lists

↓

Repeat until both lists and carry are empty

↓

Return list starting after dummy head

We add digits node by node from two lists, keep track of carry, and build a new list with the sum digits.

Execution Sample

DSA Go

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
  carry := 0
  dummy := &ListNode{}
  current := dummy
  for l1 != nil || l2 != nil || carry != 0 {
    sum := carry
    if l1 != nil {
      sum += l1.Val
      l1 = l1.Next
    }
    if l2 != nil {
      sum += l2.Val
      l2 = l2.Next
    }
    carry = sum / 10
    current.Next = &ListNode{Val: sum % 10}
    current = current.Next
  }
  return dummy.Next
}

This code adds two numbers represented by linked lists digit by digit, handling carry, and returns the sum as a linked list.

Execution Table

Step	Operation	l1 Node Value	l2 Node Value	Sum	Carry	New Node Value	List State
1	Add 2 + 5 + carry 0	2	5	7	0	7	7 -> null
2	Add 4 + 6 + carry 0	4	6	10	1	0	7 -> 0 -> null
3	Add 3 + 4 + carry 1	3	4	8	0	8	7 -> 0 -> 8 -> null
4	l1 and l2 nil, carry 0, stop	nil	nil	0	0	nil	7 -> 0 -> 8 -> null

💡 Both lists are fully traversed and carry is zero, so addition is complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
carry	0	0	1	0	0
l1	2 -> 4 -> 3	4 -> 3	3	nil	nil
l2	5 -> 6 -> 4	6 -> 4	4	nil	nil
current	dummy	node with 7	node with 0	node with 8	node with 8
result list	empty	7 -> null	7 -> 0 -> null	7 -> 0 -> 8 -> null	7 -> 0 -> 8 -> null

Key Moments - 3 Insights

Why do we continue the loop when both lists are nil but carry is not zero?

Because carry holds leftover value from previous addition, we must create a new node for it. See step 3 where carry was 1, so we added it to sum.

Why do we add sum % 10 as the new node value?

Because each node stores a single digit (0-9). sum % 10 extracts the last digit of the sum to store in the node, as shown in the 'New Node Value' column.

Why do we move l1 and l2 pointers only if they are not nil?

To avoid accessing nil nodes which causes errors. We add their values only if they exist, otherwise add zero. This is shown in the 'l1 Node Value' and 'l2 Node Value' columns.

Visual Quiz - 3 Questions

Look at the execution table, what is the carry value after step 2?

A 1

B 2

C 0

D None

💡 Hint

Check the 'Carry' column in the execution table at step 2.

At which step does the new node with value 8 get added to the list?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'New Node Value' column in the execution table.

If the first list was longer, how would the loop condition change?

A It would stop earlier

B It would continue until the longer list ends and carry is zero

C It would ignore the longer list's extra nodes

D It would cause an error

💡 Hint

Refer to the loop condition in the code and the 'exit_note' in the execution table.

Concept Snapshot

Add Two Numbers as Linked Lists:
- Traverse both lists node by node
- Sum digits + carry
- Create new node with sum % 10
- Update carry = sum / 10
- Continue until both lists and carry are done
- Return new list after dummy head

Full Transcript

This concept shows how to add two numbers represented as linked lists. We start with two lists, each node holding a digit. We keep a carry for sums over 9. We add corresponding nodes and carry, create a new node for the digit, and update carry. We move through both lists until all digits and carry are processed. The result is a new linked list representing the sum. The execution table tracks each step's sum, carry, and list state. Key moments clarify why carry is important, why we use sum % 10, and why we check for nil nodes. The visual quiz tests understanding of carry, node values, and loop behavior.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" ask you to do?

easy

A. Reverse the digits of a number stored in a linked list.

B. Multiply two numbers stored as linked lists and return the product as a linked list.

C. Add two numbers where each digit is stored in a node of a linked list, and return the sum as a linked list.

D. Find the maximum digit in a linked list representing a number.

Solution

1. Step 1: Understand the problem statement and identify the expected output

   The problem requires adding two numbers where each number is represented by a linked list, with each node holding a single digit. The sum should also be returned as a linked list, where each node contains a digit of the result.

2. Final Answer:

   Add two numbers represented as linked lists and return their sum as a linked list -> Option C

3. Quick Check:

   Adding digits node by node = Add two numbers where each digit is stored in a node of a linked list, and return the sum as a linked list. [OK]

Hint: Focus on adding digit by digit with carry [OK]

Common Mistakes:

• Confusing addition with multiplication
• Ignoring carry over between digits
• Returning a number instead of a linked list

2. Which of the following Go code snippets correctly defines a node for a singly linked list used to represent a digit in the "Add Two Numbers Represented as Linked List" problem?

easy

A. type ListNode struct { Val int; Next *ListNode }

B. type ListNode struct { Value string; Next ListNode }

C. type Node struct { Val int; Next int }

D. type ListNode struct { Val int; Next ListNode }

Solution

1. Step 1: Check struct field types and verify pointer usage

   The node should hold an integer value and a pointer to the next node, so Val is int and Next is *ListNode. Next must be a pointer to ListNode to allow linking nodes dynamically.

2. Final Answer:

   type ListNode struct { Val int; Next *ListNode } -> Option A

3. Quick Check:

   Pointer to next node = type ListNode struct { Val int; Next *ListNode } [OK]

Hint: Use *ListNode for next pointer in Go structs [OK]

Common Mistakes:

• Using value type instead of pointer for Next
• Using wrong field types like string for digits
• Missing semicolons or commas in struct

3. What will be the output linked list after adding the two numbers represented by these linked lists? List 1: 2 -> 4 -> 3 -> null (represents 342) List 2: 5 -> 6 -> 4 -> null (represents 465) Use the standard addition approach digit by digit with carry.

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 7 -> 1 -> 8 -> null

Solution

1. Step 1: Add digits from head nodes with carry and form the result linked list

   2 + 5 = 7, carry 0; next digits 4 + 6 = 10, store 0 carry 1; next digits 3 + 4 + 1 = 8. The result digits are 7 -> 0 -> 8 representing 807.

2. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

3. Quick Check:

   342 + 465 = 807 = 7->0->8 [OK]

Hint: Add digits with carry, store remainder as node value [OK]

Common Mistakes:

• Not carrying over when sum >= 10
• Adding digits in wrong order
• Confusing node values with actual number order

4. Consider this Go function snippet to add two numbers represented as linked lists. What is the bug? func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { carry := 0 dummy := &ListNode{} current := dummy for l1 != nil && l2 != nil { sum := l1.Val + l2.Val + carry carry = sum / 10 current.Next = &ListNode{Val: sum % 10} current = current.Next l1 = l1.Next l2 = l2.Next } return dummy.Next }

medium

A. The dummy node is not initialized properly.

B. Carry is not calculated correctly after sum.

C. The function does not return the correct node.

D. The loop stops when either list ends, missing remaining nodes in longer list.

Solution

1. Step 1: Analyze loop condition and identify missing processing

   The loop runs only while both l1 and l2 are not nil, so it stops if one list is longer. Remaining nodes in the longer list and any carry after loop are not handled, causing incorrect results.

2. Final Answer:

   The loop stops when either list ends, missing remaining nodes in longer list -> Option D

3. Quick Check:

   Loop condition misses longer list nodes = The loop stops when either list ends, missing remaining nodes in longer list. [OK]

Hint: Use OR condition to continue until both lists and carry are done [OK]

Common Mistakes:

• Using AND instead of OR in loop condition
• Ignoring leftover carry after loop
• Not linking remaining nodes after loop

5. You have two linked lists representing numbers in reverse order: List 1: 9 -> 9 -> 9 -> 9 -> null (represents 9999) List 2: 1 -> null (represents 1) What will be the resulting linked list after adding these two numbers?

hard

A. 0 -> 0 -> 0 -> 0 -> null

B. 0 -> 0 -> 0 -> 0 -> 1 -> null

C. 1 -> 0 -> 0 -> 0 -> 0 -> null

D. 9 -> 9 -> 9 -> 10 -> null

Solution

1. Step 1: Add digits with carry step-by-step and add final carry as new node

   9+1=10, store 0 carry 1; next 9+0+1=10, store 0 carry 1; repeat for all 9s, each time store 0 carry 1. After last 9, carry is 1, so add a new node with value 1 at the end.

2. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option B

3. Quick Check:

   9999 + 1 = 10000 = 0->0->0->0->1 [OK]

Hint: Remember to add carry node if leftover after last digit [OK]

Common Mistakes:

• Not adding extra node for leftover carry
• Stopping addition too early
• Misplacing the carry node in the list