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

Introduction

Linked lists are a popular data structure used to store a sequence of elements. They are commonly employed to represent large numbers that do not fit into standard data types, such as integers. In this article, we will explore how to add two numbers represented by linked lists in Python using the reverse method approach.

Understanding the Problem

Before diving into the solution, let’s first understand the problem we’re trying to solve. We are given two linked lists, each representing a non-negative integer, where each node in the list contains a single digit, and the digits are stored in reverse order. Our task is to add the two numbers and return the sum as a new linked list, also in reverse order.

Approach

To solve this problem, we will follow a step-by-step approach:

Python Implementation

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

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 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_two_numbers(l1, l2):
    # Add the reversed linked lists
    result = add_linked_lists(l1, l2)

    # Reverse the result back to its original order
    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(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:
7 -> 6 -> 6 -> 5 -> 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 also has a time complexity of O(N), where N is the maximum number of nodes between the two input linked lists. Since we traverse both lists simultaneously, the time complexity is proportional to the maximum number of nodes between the two lists.

4. Adding the reversed linked lists and reversing the result back: Both of these steps involve traversing the linked lists once, so they also 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` function, which encompasses all the steps, is O(N).

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, 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: Since these steps do not use any additional space other than the input and output, their space complexity is also O(1).

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` function is O(N) due to the space used for the result linked list.

Conclusion

In this article, we explored how to add two numbers represented by linked lists in Python using the reverse method approach. By reversing both linked lists, performing the addition, and then reversing the result back, we were able to solve the problem efficiently. Linked lists provide an elegant solution for handling large numbers that cannot be directly represented by standard data types.

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