Add Two Polynomials Represented as Linked Lists

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. The coefficient of the term **9**x4 is 9.
power: an integer representing the exponent. The power of the term 9x**4** is 4.
next: a pointer to the next node in the list, or null if it is the last node of the list.

For example, the polynomial 5x^3 + 4x - 7 is represented by the polynomial linked list illustrated below:

graph LR;
	A("coefficient: 5<br>power:3") --> B("coefficient: 4<br>power:1") --> C("coefficient: -7<br>power:0") --> D("null")

The polynomial linked list must be in its standard form: the polynomial must be in strictly descending order by its power value. Also, terms with a coefficient of 0 are omitted.

Given two polynomial linked list heads, poly1 and poly2, add the polynomials together and return the head of the sum of the polynomials.

PolyNode format:

The input/output format is as a list of n nodes, where each node is represented as its [coefficient, power]. For example, the polynomial 5x3 + 4x - 7 would be represented as: [[5,3],[4,1],[-7,0]].

Examples

Example 1

graph TB;
	subgraph poly1
		A("coefficient: 1<br>power:1"):::right --> B("null"):::right
	end
	subgraph poly2
		C(" "):::hidden ~~~ D("coefficient: 1<br>power:0") --> E("null"):::right
	end	

	poly1 ~~~ poly2
classDef hidden display:none;
classDef right align:center;

graph LR;
	A("coefficient: 1<br>power:1"):::right ---> B("null"):::right
	C(" "):::hidden ~~~ D("coefficient: 1<br>power:0") --> E("null"):::right

classDef hidden display:none;
classDef right align:center;

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

Example 2

Input: poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]
Output: [[5,2],[2,0]]
Explanation: poly1 = 2x2 + 4x + 3. poly2 = 3x2 - 4x - 1. The sum is 5x2 + 2. Notice that we omit the "0x" term.

Example 3

Input: poly1 = [[1,2]], poly2 = [[-1,2]]
Output: []
Explanation: The sum is 0. We return an empty list.

Solution

Method 1 – Two Pointers Merge

Intuition

The key idea is to traverse both polynomial linked lists simultaneously, comparing the powers of the current nodes. Since both lists are sorted in descending order of power, we can merge them similarly to merging two sorted lists. When powers match, sum the coefficients; if the sum is non-zero, add to the result. If powers differ, add the term with the higher power to the result.

Approach

Initialize a dummy node to build the result list and a pointer cur to track the current node.
Use two pointers, p1 and p2, to traverse poly1 and poly2.
While both pointers are not null:
- If p1.power > p2.power, append p1's term to the result and move p1 forward.
- If p1.power < p2.power, append p2's term to the result and move p2 forward.
- If p1.power == p2.power, sum the coefficients. If the sum is not zero, create a new node with the sum and the same power, and append to the result. Move both pointers forward.
Append any remaining nodes from either list.
Return the next node of the dummy as the head of the result.

Code

C++

class Solution {
public:
	 PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
		  PolyNode dummy(0, 0);
		  PolyNode* ans = &dummy;
		  while (poly1 && poly2) {
				if (poly1->power > poly2->power) {
					 ans->next = poly1;
					 poly1 = poly1->next;
				} else if (poly1->power < poly2->power) {
					 ans->next = poly2;
					 poly2 = poly2->next;
				} else {
					 int sum = poly1->coefficient + poly2->coefficient;
					 if (sum != 0) {
						  ans->next = new PolyNode(sum, poly1->power);
						  ans = ans->next;
					 }
					 poly1 = poly1->next;
					 poly2 = poly2->next;
					 continue;
				}
				ans = ans->next;
		  }
		  ans->next = poly1 ? poly1 : poly2;
		  return dummy.next;
	 }
};

Go

func addPoly(poly1 *PolyNode, poly2 *PolyNode) *PolyNode {
	 dummy := &PolyNode{}
	 ans := dummy
	 for poly1 != nil && poly2 != nil {
		  if poly1.Power > poly2.Power {
				ans.Next = poly1
				poly1 = poly1.Next
				ans = ans.Next
		  } else if poly1.Power < poly2.Power {
				ans.Next = poly2
				poly2 = poly2.Next
				ans = ans.Next
		  } else {
				sum := poly1.Coefficient + poly2.Coefficient
				if sum != 0 {
					 ans.Next = &PolyNode{Coefficient: sum, Power: poly1.Power}
					 ans = ans.Next
				}
				poly1 = poly1.Next
				poly2 = poly2.Next
		  }
	 }
	 if poly1 != nil {
		  ans.Next = poly1
	 } else {
		  ans.Next = poly2
	 }
	 return dummy.Next
}

Java

class Solution {
	 public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
		  PolyNode dummy = new PolyNode(0, 0);
		  PolyNode ans = dummy;
		  while (poly1 != null && poly2 != null) {
				if (poly1.power > poly2.power) {
					 ans.next = poly1;
					 poly1 = poly1.next;
					 ans = ans.next;
				} else if (poly1.power < poly2.power) {
					 ans.next = poly2;
					 poly2 = poly2.next;
					 ans = ans.next;
				} else {
					 int sum = poly1.coefficient + poly2.coefficient;
					 if (sum != 0) {
						  ans.next = new PolyNode(sum, poly1.power);
						  ans = ans.next;
					 }
					 poly1 = poly1.next;
					 poly2 = poly2.next;
				}
		  }
		  ans.next = (poly1 != null) ? poly1 : poly2;
		  return dummy.next;
	 }
}

Kotlin

class Solution {
	 fun addPoly(poly1: PolyNode?, poly2: PolyNode?): PolyNode? {
		  val dummy = PolyNode(0, 0)
		  var ans = dummy
		  var p1 = poly1
		  var p2 = poly2
		  while (p1 != null && p2 != null) {
				when {
					 p1.power > p2.power -> {
						  ans.next = p1
						  p1 = p1.next
						  ans = ans.next!!
					 }
					 p1.power < p2.power -> {
						  ans.next = p2
						  p2 = p2.next
						  ans = ans.next!!
					 }
					 else -> {
						  val sum = p1.coefficient + p2.coefficient
						  if (sum != 0) {
								ans.next = PolyNode(sum, p1.power)
								ans = ans.next!!
						  }
						  p1 = p1.next
						  p2 = p2.next
					 }
				}
		  }
		  ans.next = p1 ?: p2
		  return dummy.next
	 }
}

Python

class Solution:
	 def addPoly(self, poly1: 'PolyNode | None', poly2: 'PolyNode | None') -> 'PolyNode | None':
		  dummy = PolyNode(0, 0)
		  ans = dummy
		  while poly1 and poly2:
				if poly1.power > poly2.power:
					 ans.next = poly1
					 poly1 = poly1.next
					 ans = ans.next
				elif poly1.power < poly2.power:
					 ans.next = poly2
					 poly2 = poly2.next
					 ans = ans.next
				else:
					 s = poly1.coefficient + poly2.coefficient
					 if s != 0:
						  ans.next = PolyNode(s, poly1.power)
						  ans = ans.next
					 poly1 = poly1.next
					 poly2 = poly2.next
		  ans.next = poly1 if poly1 else poly2
		  return dummy.next

Rust

impl Solution {
	 pub fn add_poly(mut poly1: Option<Box<PolyNode>>, mut poly2: Option<Box<PolyNode>>) -> Option<Box<PolyNode>> {
		  let mut dummy = Box::new(PolyNode::new(0, 0));
		  let mut ans = &mut dummy;
		  while poly1.is_some() && poly2.is_some() {
				let (c1, p1) = {
					 let node = poly1.as_ref().unwrap();
					 (node.coefficient, node.power)
				};
				let (c2, p2) = {
					 let node = poly2.as_ref().unwrap();
					 (node.coefficient, node.power)
				};
				if p1 > p2 {
					 let next = poly1.as_mut().unwrap().next.take();
					 ans.next = poly1;
					 ans = ans.next.as_mut().unwrap();
					 poly1 = next;
				} else if p1 < p2 {
					 let next = poly2.as_mut().unwrap().next.take();
					 ans.next = poly2;
					 ans = ans.next.as_mut().unwrap();
					 poly2 = next;
				} else {
					 let sum = c1 + c2;
					 if sum != 0 {
						  ans.next = Some(Box::new(PolyNode::new(sum, p1)));
						  ans = ans.next.as_mut().unwrap();
					 }
					 poly1 = poly1.unwrap().next;
					 poly2 = poly2.unwrap().next;
				}
		  }
		  ans.next = if poly1.is_some() { poly1 } else { poly2 };
		  dummy.next
	 }
}

Complexity

⏰ Time complexity: O(n + m), where n and m are the lengths of the two lists.
🧺 Space complexity: O(n + m) for the result list.