Python Program to Add Two Numbers Represented by Linked Lists

Overview

This Python program adds two numbers represented by two linked lists, where each node contains a single digit of the number. The digits are stored in reverse order, meaning that the least significant digit comes first. The program outputs the sum of the two numbers as a new linked list, also in reverse order.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list and a function to add two linked lists representing numbers.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has two attributes: data (the value of the node) and next (pointer to the next node).
2. Create a function add_two_numbers that takes two linked list heads and adds the numbers they represent.
3. Use an iterative approach to traverse both linked lists simultaneously, adding the corresponding digits along with any carry from the previous addition.
4. Create a new linked list to store the result. If the sum of two digits exceeds 9, carry over the excess to the next digit.

Python Code


class Node:
"""
Node class to represent a linked list node.
Each node contains the data and a pointer to the next node.
"""
def __init__(self, data):
self.data = data
self.next = None

def add_two_numbers(list1, list2):
“””
Add two numbers represented by linked lists.

:param list1: Head node of the first linked list
:param list2: Head node of the second linked list
:return: Head node of the resulting linked list representing the sum
“””
dummy = Node(0)
current = dummy
carry = 0

while list1 is not None or list2 is not None or carry != 0:
# Get the current values, or 0 if the list has been exhausted
val1 = list1.data if list1 is not None else 0
val2 = list2.data if list2 is not None else 0

# Calculate the sum and carry
total = val1 + val2 + carry
carry = total // 10 # Carry is the tens place
current.next = Node(total % 10) # Add the ones place as a new node

# Move pointers forward
current = current.next
if list1 is not None:
list1 = list1.next
if list2 is not None:
list2 = list2.next

return dummy.next # The result is the next node after the dummy

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create two numbers: 342 (represented as 2 -> 4 -> 3) and 465 (represented as 5 -> 6 -> 4)
num1 = Node(2)
num1.next = Node(4)
num1.next.next = Node(3)

num2 = Node(5)
num2.next = Node(6)
num2.next.next = Node(4)

print(“First Number Linked List:”)
print_linked_list(num1)

print(“Second Number Linked List:”)
print_linked_list(num2)

# Add the two numbers
result = add_two_numbers(num1, num2)

print(“Resulting Linked List After Addition:”)
print_linked_list(result)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data) and a reference to the next node (next).
• add_two_numbers function: Adds the two numbers represented by the linked lists. It iterates through both lists, adding the corresponding digits and handling the carry for sums greater than 9.
• print_linked_list function: A utility function to display the linked lists before and after the addition operation.

Example Output

Given two linked lists representing the numbers 342 and 465:

• First Number: 2 -> 4 -> 3 -> None (which represents 342)
• Second Number: 5 -> 6 -> 4 -> None (which represents 465)

The resulting sum will be:

7 -> 0 -> 8 -> None (which represents 807)