Adding Two Numbers Represented by Linked Lists in Python using Forward Method

Introduction

Linked lists are a versatile data structure often used to handle large numbers that don’t fit into standard data types, such as integers. When given two linked lists representing non-negative integers in forward order, our goal is to add the numbers and return the sum as a new linked list, also in forward order. In this article, we’ll explore an efficient Python approach to achieve this.

Understanding the Problem

Before diving into the solution, let’s understand the challenge at hand. We are provided with two linked lists, where each node contains a single digit of a non-negative integer. The digits are stored in forward order, i.e., the most significant digit comes first. Our task is to add these two numbers and create a new linked list to represent the sum, also in forward order.

Approach

To solve the problem, we’ll use the following steps:

Python Implementation

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

def add_linked_lists(l1, l2):
    dummy_head = ListNode()
    current = dummy_head
    carry = 0

    while l1 or l2 or carry:
        # Calculate the sum of the current digits and the carry
        sum_value = carry
        if l1:
            sum_value += l1.value
            l1 = l1.next
        if l2:
            sum_value += l2.value
            l2 = l2.next

        # Update the carry for the next iteration
        carry = sum_value // 10
        sum_value = sum_value % 10

        # Append the new node with the sum value
        current.next = ListNode(sum_value)
        current = current.next

    return dummy_head.next

def add_two_numbers_forward(l1, l2):
    # Reverse both linked lists to simplify addition
    l1 = reverse_linked_list(l1)
    l2 = reverse_linked_list(l2)

    # Add the reversed linked lists
    result = add_linked_lists(l1, l2)

    # Reverse the result back to get the final output
    result = reverse_linked_list(result)

    return result

# Helper function to convert a list to a linked list
def list_to_linked_list(lst):
    dummy_head = ListNode()
    current = dummy_head

    for value in lst:
        current.next = ListNode(value)
        current = current.next

    return dummy_head.next

# Helper function to convert a linked list to a list
def linked_list_to_list(head):
    result = []
    current = head

    while current:
        result.append(current.value)
        current = current.next

    return result

def print_list(num_list):
    for i in num_list:
        print(i, '-> ', end='')
    print("None")

# Example usage:
num1 = [9, 8, 7, 6]
num2 = [6, 7, 8] 

l1 = list_to_linked_list(num1)
l2 = list_to_linked_list(num2)

result_linked_list = add_two_numbers_forward(l1, l2)
result_list = linked_list_to_list(result_linked_list)

print("First List:")
print_list(num1)

print("Second List:")
print_list(num2)

print("Final List:")
print_list(result_list)

Output

First List:
9 -> 8 -> 7 -> 6 -> None
Second List:
6 -> 7 -> 8 -> None
Final List:
1 -> 0 -> 5 -> 5 -> 4 -> None

Complexity Analysis

Let’s analyze the time and space complexity of the above program:

Time Complexity

1. Converting lists to linked lists: The helper functions `list_to_linked_list` and `linked_list_to_list` both have a time complexity of O(N), where N is the number of elements in the input list. This is because we need to traverse the entire list to create the linked list or convert it back to a list.

2. Reversing a linked list: The `reverse_linked_list` function has a time complexity of O(N), where N is the number of nodes in the linked list. In this function, we traverse the entire linked list once and reverse the pointers, which takes linear time.

3. Adding two linked lists: The `add_linked_lists` function iterates through both input linked lists simultaneously. Since we visit each node once, the time complexity for this step is O(N), where N is the maximum number of nodes between the two input linked lists.

4. Adding the reversed linked lists and reversing the result back: Both of these steps involve traversing the linked lists once, so they have a time complexity of O(N).

5. Printing the List: The `print_list` function has a time complexity of O(N), where N is the number of elements in the given list.

Overall, the time complexity of the `add_two_numbers_forward` function, which includes all the above steps, is O(N), where N is the maximum number of nodes between the two input linked lists.

Space Complexity

1. Converting lists to linked lists: The `list_to_linked_list` function creates a new linked list with N nodes, so it has a space complexity of O(N). Similarly, the `linked_list_to_list` function creates a list with N elements, leading to a space complexity of O(N).

2. Reversing a linked list: The `reverse_linked_list` function uses a constant amount of extra space to reverse the pointers, so it has a space complexity of O(1).

3. Adding two linked lists and creating the result: In the `add_linked_lists` function, we create a new linked list to store the result. The space required for the new linked list is proportional to the maximum number of nodes between the two input lists, so the space complexity for this step is O(N).

4. Adding the reversed linked lists and reversing the result back: These steps also involve creating new linked lists with space complexity of O(N), where N is the number of nodes in the original linked lists.

5. Printing the List: The `print_list` function doesn’t take any additional space, therefore the space complexity is O(1). 

Overall, the space complexity of the `add_two_numbers_forward` function is O(N) due to the space used for the result linked list.

Conclusion

In this article, we explored an efficient Python approach to add two numbers represented by linked lists in forward order. By first reversing the linked lists, performing the addition, and then reversing the result back, we were able to tackle this challenge effectively. Linked lists provide an elegant solution for dealing with large numbers that exceed standard data type capacities, making them a valuable data structure for various applications.

If you have any questions related to this topic, please don’t hesitate to leave your comments below.