FunctionRacerProblemsRace

Multiply Two Polynomials

HardLinked listsPython, JavaScript, TypeScript, Java, C++

A polynomial is stored as a linked list of pairs: a coefficient in one node and its power in the next. The pairs come from the highest power down, every power appears once, and no coefficient is 0. So 3 -> 2 -> -1 -> 0 stands for 3x^2 - 1. An empty list is the polynomial 0.

Return the product of the two polynomials in the same form: highest power first, each power once, and no term with coefficient 0. The lists are passed in as first and second.

Linked lists appear in the tests as the list of their values, like [1,2,3]. Each node is a ListNode with .val and .next; the class is already defined for you.

Example 1

first [1,1,1,0]
second [1,1,-1,0]
returns [1,2,-1,0]

(x + 1)(x - 1) = x^2 - 1. The two terms with x cancel out and are left away.

Example 2

first [2,3]
second [3,2]
returns [6,5]

2x^3 times 3x^2 is 6x^5.

Example 3

first []
second [1,0]
returns []

Anything times 0 is 0, the empty list.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Linked lists problems