Problem statement

https://leetcode.com/problems/add-two-polynomials-represented-as-linked-lists/

Solution

The idea is to use two pointers: each for each polynomial and check conditions:

  1. if power p1 is greater than power p2, we connect PolyNode(c1, p1).
  2. Similar logic if p2 > p1.
  3. If they are equal, we connect their sum.

Also, we move pointer in poly1 if p1 >= p2, similar logic for the second one. Finally, do not forgot to check if p1 == p2 and c1 + c2 == 0, in this case we need to continuet traverse.

Complexity

Time complexity is O(n + m), space complexity is O(n + m)

Code

class Solution:
    def addPoly(self, poly1, poly2):
        poly3 = ans = PolyNode(0, float("inf"))
        
        while poly1 or poly2:
            p1 = poly1.power if poly1 else -1
            p2 = poly2.power if poly2 else -1
            c1 = poly1.coefficient if poly1 else 0
            c2 = poly2.coefficient if poly2 else 0

            if p1 >= p2: poly1 = poly1.next
            if p1 <= p2: poly2 = poly2.next
            if p1 == p2 and c1 + c2 == 0: continue
                
            if p1 > p2:
                ans.next = PolyNode(c1, p1)
            elif p1 < p2:
                ans.next = PolyNode(c2, p2)
            else:
                ans.next = PolyNode(c1 + c2, p1)
           
            ans = ans.next
            
        return poly3.next