Add Two Numbers Represented as Linked List in DSA Go - Build from Scratch

Add Two Numbers Represented as Linked List

📖 Scenario: You are working on a simple calculator app that adds two numbers. These numbers are stored in reverse order as linked lists, where each node contains a single digit. Your task is to add these two numbers and return the sum as a linked list in the same reverse order.

🎯 Goal: Build a Go program that creates two linked lists representing numbers, adds them digit by digit, and prints the resulting linked list showing the sum.

📋 What You'll Learn

Create two linked lists representing the numbers 342 and 465 in reverse order

Create a variable to hold the carry during addition

Write a loop to add corresponding digits and carry, creating a new linked list for the sum

Print the resulting linked list in the format: 7 -> 0 -> 8 -> null

💡 Why This Matters

🌍 Real World

Adding numbers digit by digit is similar to how calculators or computers handle large number arithmetic internally.

💼 Career

Understanding linked lists and how to manipulate them is important for software engineering roles that involve data structures and algorithm problem solving.

1

Create two linked lists representing numbers

Create a linked list node struct called ListNode with an int field called Val and a pointer to ListNode called Next. Then create two linked lists called l1 and l2 representing the numbers 342 and 465 in reverse order. For l1, create nodes with values 2, 4, 3. For l2, create nodes with values 5, 6, 4.

DSA Go

// Define ListNode struct and create linked lists l1 and l2
// Your code here

Hint

Start by defining the ListNode struct with Val and Next. Then create l1 and l2 with the exact values in reverse order.

2

Create a carry variable for addition

Inside the main function, create an integer variable called carry and set it to 0. Also create a dummy head node called dummyHead of type *ListNode with value 0. Create a pointer called current that points to dummyHead.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}

    // Create carry variable and dummy head node
    // Your code here
}

Hint

Create carry as 0 to hold the carry digit. Use dummyHead as a starting node for the result list and current to build the list.

3

Add the two numbers digit by digit

Write a for loop that continues while l1 != nil or l2 != nil or carry != 0. Inside the loop, create variables val1 and val2 to hold the current digits from l1 and l2 or 0 if the node is nil. Calculate the sum of val1, val2, and carry. Update carry to sum / 10. Create a new node with value sum % 10 and set current.Next to this node. Move current to current.Next. Move l1 and l2 to their next nodes if they are not nil.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}

    carry := 0
    dummyHead := &ListNode{Val: 0}
    current := dummyHead

    // Add digits from l1 and l2 with carry
    // Your code here
}

Hint

Use a loop to add digits and carry. Use val1 and val2 to handle nil nodes. Update carry and create new nodes for the sum.

4

Print the resulting linked list

Write a for loop to print the values of the linked list starting from dummyHead.Next. Print each node's Val followed by -> . After the loop, print null to indicate the end of the list.

DSA Go

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}

    carry := 0
    dummyHead := &ListNode{Val: 0}
    current := dummyHead

    for l1 != nil || l2 != nil || carry != 0 {
        val1 := 0
        if l1 != nil {
            val1 = l1.Val
        }
        val2 := 0
        if l2 != nil {
            val2 = l2.Val
        }

        sum := val1 + val2 + carry
        carry = sum / 10
        current.Next = &ListNode{Val: sum % 10}
        current = current.Next

        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }

    // Print the resulting linked list
    // Your code here
}

Hint

Use a loop to go through the result list starting at dummyHead.Next. Print each value followed by -> . After the loop, print null.

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