Problem Description

This problem asks you to add two polynomials that are represented as linked lists and return the sum as a new polynomial linked list.

Each node in the polynomial linked list represents one term of the polynomial and contains:

• coefficient: The numerical multiplier of the term (e.g., in 9x^4, the coefficient is 9)
• power: The exponent of the variable (e.g., in 9x^4, the power is 4)
• next: A pointer to the next term in the polynomial

The polynomial linked lists follow these rules:

• Terms are arranged in strictly descending order by their power values
• Terms with a coefficient of 0 are not included in the list

For example, the polynomial 5x^3 + 4x - 7 would be represented as a linked list with three nodes:

• First node: coefficient=5, power=3 (representing 5x^3)
• Second node: coefficient=4, power=1 (representing 4x)
• Third node: coefficient=-7, power=0 (representing -7)

Your task is to:

1. Take two polynomial linked lists (poly1 and poly2)
2. Add them together by combining like terms (terms with the same power)
3. Return the head of a new linked list representing the sum
4. Ensure the result maintains descending power order and excludes any terms with coefficient 0

For instance, if you add (5x^3 + 4x - 7) and (3x^3 - 2x^2 + 6), the result would be (8x^3 - 2x^2 + 4x - 1).

Intuition

When adding two polynomials manually, we combine terms with the same power. For example, 3x^2 + 5x^2 = 8x^2. Since both linked lists are already sorted in descending order by power, we can traverse them simultaneously using a two-pointer approach, similar to merging two sorted lists.

Think of it like merging two sorted arrays, but with a twist. As we traverse both lists:

• If one polynomial has a term with a higher power than the other, that term appears in the result unchanged (since there's no matching term to add to it)
• If both polynomials have terms with the same power, we add their coefficients together
• If the sum of coefficients equals zero, we skip that term entirely (as per the problem's requirement)

The key insight is that we don't need to collect all terms first and then sort them. Since both input lists are already sorted, we can build the result in sorted order directly by comparing powers at each step.

We use a dummy head node to simplify the list construction - this eliminates the need for special handling of the first node. We maintain a curr pointer to track where we're building the result list.

After processing all matching terms, one list might still have remaining terms (with lower powers than anything in the other list). These remaining terms can be directly appended to our result since there are no corresponding terms to add them with.

This approach processes each term exactly once, making it efficient with O(m + n) time complexity where m and n are the lengths of the two input polynomial lists.

Learn more about Linked List, Math and Two Pointers patterns.

Solution Approach

The implementation uses a two-pointer technique to traverse both polynomial linked lists simultaneously while building the result list.

Step-by-step implementation:

1. Initialize pointers and dummy node:

   • Create a dummy head node to simplify list construction: dummy = curr = PolyNode()
   • curr will be used to build the result list

2. Main traversal loop - process both lists while both have nodes:

   while poly1 and poly2:

   At each iteration, we compare the powers of the current nodes:

   • Case 1: poly1.power > poly2.power

     • The term from poly1 has no matching term in poly2
     • Add this node directly to the result: curr.next = poly1
     • Advance poly1 and curr pointers

   • Case 2: poly1.power < poly2.power

     • The term from poly2 has no matching term in poly1
     • Add this node directly to the result: curr.next = poly2
     • Advance poly2 and curr pointers

   • Case 3: poly1.power == poly2.power

     • Both polynomials have terms with the same power - we need to add coefficients
     • Calculate sum: c = poly1.coefficient + poly2.coefficient
     • Using the walrus operator :=, we check if the sum is non-zero:

       if c := poly1.coefficient + poly2.coefficient:
           curr.next = PolyNode(c, poly1.power)
           curr = curr.next

     • If the sum is 0, we skip creating a node (terms cancel out)
     • Advance both poly1 and poly2 pointers regardless of whether we created a node

3. Handle remaining nodes:

   curr.next = poly1 or poly2

   After the main loop, one list might have remaining nodes (the one with smaller powers). We append all remaining nodes directly since there are no corresponding terms to add.

4. Return the result:

   return dummy.next

   Skip the dummy head and return the actual head of the result list.

Key optimizations:

• We reuse existing nodes when possible (Cases 1 and 2) instead of creating new ones
• The walrus operator := allows us to compute and check the coefficient sum in one expression
• The expression poly1 or poly2 elegantly handles appending remaining nodes from whichever list is non-empty

This approach maintains the required descending power order naturally and automatically excludes zero-coefficient terms.

Example Walkthrough

Let's walk through adding two polynomials step by step:

• poly1: 3x^2 + 2x (represented as [3,2] -> [2,1])
• poly2: x^2 - 2x + 1 (represented as [1,2] -> [-2,1] -> [1,0])

Initial Setup:

• Create dummy node and curr pointer
• poly1 points to [3,2]
• poly2 points to [1,2]

Iteration 1:

• Compare powers: poly1.power = 2, poly2.power = 2 (equal)
• Add coefficients: 3 + 1 = 4
• Since 4 ≠ 0, create new node [4,2]
• Advance both pointers: poly1 → [2,1], poly2 → [-2,1]
• Result so far: dummy -> [4,2]

Iteration 2:

• Compare powers: poly1.power = 1, poly2.power = 1 (equal)
• Add coefficients: 2 + (-2) = 0
• Since sum is 0, skip creating a node (terms cancel out)
• Advance both pointers: poly1 → null, poly2 → [1,0]
• Result remains: dummy -> [4,2]

After main loop:

• poly1 is null, poly2 still has [1,0]
• Append remaining: curr.next = poly2
• Final result: dummy -> [4,2] -> [1,0]

Return: 4x^2 + 1 (skipping the dummy head)

This demonstrates how the algorithm:

1. Merges terms with matching powers by adding coefficients
2. Automatically excludes zero-coefficient terms
3. Maintains descending power order
4. Efficiently handles remaining terms

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n) where m is the number of nodes in poly1 and n is the number of nodes in poly2.

The algorithm traverses both linked lists exactly once. In each iteration of the while loop, we advance at least one pointer (either poly1, poly2, or both). The loop continues until both lists are fully traversed. Each node from both polynomials is visited exactly once, resulting in linear time complexity relative to the total number of nodes.

Space Complexity: O(1) for auxiliary space, or O(min(m, n)) if we consider the output space.

The algorithm uses only a constant amount of extra space for the dummy and curr pointers. However, when two nodes have the same power and their coefficients sum to a non-zero value, a new node is created. In the worst case, all nodes from the shorter polynomial could have matching powers with the longer one, creating up to min(m, n) new nodes. For nodes where powers don't match or when one list is exhausted, the algorithm reuses existing nodes by adjusting pointers rather than creating new ones.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Lists Instead of Creating New Nodes

The Pitfall: In the current implementation, when powers don't match (Cases 1 and 2), we directly link to existing nodes from the input lists:

if poly1.power > poly2.power:
    current.next = poly1  # Reusing original node!
    poly1 = poly1.next
    current = current.next

This means the result list shares nodes with the input lists. If the caller later modifies either input list, it will inadvertently modify the result list too. This violates the principle of immutability and can lead to unexpected bugs.

Example Scenario:

# Original lists
poly1: 5x^3 -> 4x -> -7
poly2: 3x^2 -> 6

# After addition, result shares nodes
result: 5x^3 -> 3x^2 -> 4x -> -1

# If someone modifies poly1's first node later:
poly1.coefficient = 10  # Changes 5x^3 to 10x^3

# The result is now corrupted:
result: 10x^3 -> 3x^2 -> 4x -> -1  # Unexpected change!

The Solution: Always create new nodes for the result to ensure complete independence:

class Solution:
    def addPoly(self, poly1: "PolyNode", poly2: "PolyNode") -> "PolyNode":
        dummy_head = PolyNode()
        current = dummy_head
      
        while poly1 and poly2:
            if poly1.power > poly2.power:
                # Create a new node instead of reusing
                current.next = PolyNode(poly1.coefficient, poly1.power)
                poly1 = poly1.next
                current = current.next
            elif poly1.power < poly2.power:
                # Create a new node instead of reusing
                current.next = PolyNode(poly2.coefficient, poly2.power)
                poly2 = poly2.next
                current = current.next
            else:
                coefficient_sum = poly1.coefficient + poly2.coefficient
                if coefficient_sum != 0:
                    current.next = PolyNode(coefficient_sum, poly1.power)
                    current = current.next
                poly1 = poly1.next
                poly2 = poly2.next
      
        # Handle remaining terms - create new nodes
        while poly1:
            current.next = PolyNode(poly1.coefficient, poly1.power)
            current = current.next
            poly1 = poly1.next
          
        while poly2:
            current.next = PolyNode(poly2.coefficient, poly2.power)
            current = current.next
            poly2 = poly2.next
          
        return dummy_head.next

2. Forgetting to Handle Zero Coefficients After Addition

The Pitfall: When adding terms with the same power, beginners often forget to check if the sum equals zero:

# WRONG - creates unnecessary zero-coefficient nodes
if poly1.power == poly2.power:
    current.next = PolyNode(poly1.coefficient + poly2.coefficient, poly1.power)
    current = current.next
    poly1 = poly1.next
    poly2 = poly2.next

This violates the problem requirement that terms with coefficient 0 should not be included in the result.

Example: Adding 3x^2 and -3x^2 would incorrectly produce a node with 0x^2 instead of omitting it entirely.

The Solution: Always check if the coefficient sum is non-zero before creating a node, as shown in the correct implementation above.