What is the time complexity of LeetCode 1634. Add Two Polynomials Represented as Linked Lists?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 1634. Add Two Polynomials Represented as Linked Lists?

The Python solution on this page uses O(1) auxiliary space.

Add Two Polynomials Represented as Linked Lists — LeetCode 1634 Python Solution

MediumLeetCode PremiumLinked ListMathTwo Pointers

Problem: #1634
Pattern: Linked List
Reading time: 5 min
Source: leetcode.com

The problem

A polynomial linked list is a special type of linked list where every node represents a term in a polynomial expression. Each node has three attributes: coefficient: an integer representing the number multiplier of the term.

Example

Input: poly1 = [[1,1]], poly2 = [[1,0]]
Output: [[1,1],[1,0]]
Explanation: poly1 = x. poly2 = 1. The sum is x + 1.

Python solution

Python

# Definition for polynomial singly-linked list.
# class PolyNode:
#     def __init__(self, x=0, y=0, next=None):
#         self.coefficient = x
#         self.power = y
#         self.next = next


class Solution:
    def addPoly(self, poly1: "PolyNode", poly2: "PolyNode") -> "PolyNode":
        dummy = curr = PolyNode()
        while poly1 and poly2:
            if poly1.power > poly2.power:
                curr.next = poly1
                poly1 = poly1.next
                curr = curr.next
            elif poly1.power < poly2.power:
                curr.next = poly2
                poly2 = poly2.next
                curr = curr.next
            else:
                if c := poly1.coefficient + poly2.coefficient:
                    curr.next = PolyNode(c, poly1.power)
                    curr = curr.next
                poly1 = poly1.next
                poly2 = poly2.next
        curr.next = poly1 or poly2
        return dummy.next

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1634. Add Two Polynomials Represented as Linked Lists is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1634. Add Two Polynomials Represented as Linked Lists?: LeetCode 1634. Add Two Polynomials Represented as Linked Lists is rated Medium on LeetCode.
What is the time complexity of LeetCode 1634. Add Two Polynomials Represented as Linked Lists?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 1634. Add Two Polynomials Represented as Linked Lists?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1634. Add Two Polynomials Represented as Linked Lists cover?: LeetCode 1634. Add Two Polynomials Represented as Linked Lists is tagged Linked List, Math and Two Pointers on LeetCode.
Is LeetCode 1634. Add Two Polynomials Represented as Linked Lists a premium problem?: Yes. LeetCode 1634. Add Two Polynomials Represented as Linked Lists is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.