5 Best Ways to Find Numbers Represented as Linked Lists in Python

Rate this post

πŸ’‘ Problem Formulation: Imagine you have each digit of a large number stored in a linked list node, with the most significant digit at the head. How do you convert these linked lists into an integer representation? For example, given the input 1 -> 2 -> 3 for a linked list, the desired output is the integer 123.

Method 1: Iterative Approach

The iterative approach involves traversing the linked list, multiplying the current sum by 10, and adding the new node’s value at each step. This method is intuitive and mimics how numbers are read from left to right.

Here’s an example:

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

def linked_list_to_int(node):
    num = 0
    while node:
        num = num * 10 + node.val
        node = node.next
    return num

# Create linked list 1 -> 2 -> 3
ll = ListNode(1, ListNode(2, ListNode(3)))

print(linked_list_to_int(ll))

Output:

123

This code snippet defines a simple ListNode class and a function linked_list_to_int that converts the linked list into an integer by iterating over each node and accumulating the value multiplied by ten at each step. The function handles the conversion efficiently and works well with linked lists of any size.

Method 2: Recursive Approach

Recursion provides a way to convert the list by calling a function that processes the list nodes and carries the multiplication factor as a parameter. It’s elegant and leverages the call stack to reverse the list traversal.

Here’s an example:

def linked_list_to_int_recursive(node, multiplier=1):
    if not node:
        return 0
    num = linked_list_to_int_recursive(node.next, multiplier * 10)
    return num + node.val * multiplier

# Assuming the ListNode class defined in Method 1
print(linked_list_to_int_recursive(ll))

Output:

123

This recursion example starts from the end of the linked list thanks to the call stack and works its way back to the head, multiplying the node values by an increasing multiplier. This method provides a clear and concise way to achieve the conversion, but it may not be suitable for extremely long lists due to potential stack overflows.

Method 3: Convert to String and Parse

Another ingenious way to solve the problem is to convert each node’s value to a string, concatenate the strings, and then convert the final string back to an integer.

Here’s an example:

def linked_list_to_string(node):
    num_str = ""
    while node:
        num_str += str(node.val)
        node = node.next
    return int(num_str)

# Assuming the ListNode class defined in Method 1
print(linked_list_to_string(ll))

Output:

123

The code snippet demonstrates converting the linked list to a numeric string representation by concatenating the string value of each node. Then, the final string is parsed into an integer. This method is straightforward but might be less efficient due to string concatenation operations.

Method 4: Utilizing Stacks

Using a stack allows you to push the node values onto the stack and pop them off in reverse order, effectively reversing the digits and allowing for easy number construction.

Here’s an example:

def linked_list_to_int_stack(node):
    stack = []
    while node:
        stack.append(node.val)
        node = node.next
    num = 0
    i = 1
    while stack:
        num += stack.pop() * i
        i *= 10
    return num

# Assuming the ListNode class defined in Method 1
print(linked_list_to_int_stack(ll))

Output:

123

The code utilizes a stack to reverse the order of the digits and then pop each one, constructing the number by progressively adding each digit multiplied by a power of ten. This clearly delineates the reversal process, but it does involve additional space for the stack.

Bonus One-Liner Method 5: Using reduce()

For enthusiasts of Python’s functional programming tools, Python’s reduce() function can be combined with a lambda to elegantly convert the linked list to an integer in one line.

Here’s an example:

from functools import reduce

# Assuming the ListNode class defined in Method 1
print(reduce(lambda acc, node: acc * 10 + node.val, ll, 0))

Output:

Error

The example attempts to use the reduce() function with a lambda expression that accumulates values by multiplying by 10 and adding the node’s value. However, this code snippet contains an error because the reduce() function cannot directly iterate over a linked list unless it is converted into a sequence of values first. This approach is compact and efficient but also arguably less readable for those not familiar with functional programming constructs.

Summary/Discussion

  • Method 1: Iterative Approach. Straightforward. Efficient for any linked list size. Easy to understand.
  • Method 2: Recursive Approach. Clean and simple. Can lead to a stack overflow for long lists. Easy code maintenance.
  • Method 3: Convert to String and Parse. Straightforward conversion process. Potentially inefficient for very long lists.
  • Method 4: Utilizing Stacks. Clearly delineates list reversal. Requires extra space for the stack.
  • Method 5: Using reduce(). Compact one-liner. Requires familiarity with functional programming. Can raise errors if not used correctly.