Add Two Numbers Represented by Linked Lists in Go

Program Code

package main

import "fmt"

// ListNode defines a node in a singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// addTwoNumbers adds two numbers represented by linked lists
func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy
    carry := 0

    // Traverse both linked lists
    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
}

// Helper function to print the linked list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

// Main function to test the addTwoNumbers function
func main() {
    // Create two linked lists representing numbers
    // List 1: 2 -> 4 -> 3 (represents number 342)
    // List 2: 5 -> 6 -> 4 (represents number 465)
    // Sum: 7 -> 0 -> 8 (represents number 807)

    // Create the first number
    l1 := &ListNode{2, &ListNode{4, &ListNode{3, nil}}}

    // Create the second number
    l2 := &ListNode{5, &ListNode{6, &ListNode{4, nil}}}

    fmt.Print("List 1: ")
    printList(l1)

    fmt.Print("List 2: ")
    printList(l2)

    // Add the two numbers
    result := addTwoNumbers(l1, l2)

    fmt.Print("Sum List: ")
    printList(result)
}
    

Explanation

The Go program is designed to add two numbers represented by singly linked lists. Here is a detailed explanation of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list, which contains:

• Val: The value of the node (a single digit of the number).
• Next: A pointer to the next node in the list.

2. addTwoNumbers Function

The addTwoNumbers function adds two numbers represented by linked lists:

• Initializes a dummy node and a carry variable to handle the addition of digits.
• Traverses both linked lists simultaneously, adding corresponding digits and the carry:
  • Calculates the sum of the digits and the carry.
  • Determines the new carry and the value for the current node.
  • Moves to the next nodes in both linked lists and updates the carry.
• Returns the flattened list starting from the dummy node’s next pointer.

3. printList Function

The printList function is a utility to print out the values of the linked list for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the addTwoNumbers function:

• Creates two linked lists representing the numbers 342 and 465.
• Prints the original linked lists.
• Adds the two numbers using addTwoNumbers and prints the result, which represents the number 807.