Skip to content

1634. Add Two Polynomials Represented as Linked Lists 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for polynomial singly-linked list.
 * struct PolyNode {
 *   int coefficient, power;
 *   PolyNode *next;
 *   PolyNode(): coefficient(0), power(0), next(nullptr) {};
 *   PolyNode(int x, int y): coefficient(x), power(y), next(nullptr) {};
 *   PolyNode(int x, int y, PolyNode* next): coefficient(x), power(y),
 *                                           next(next) {};
 * };
 */

class Solution {
 public:
  PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
    PolyNode* dummy = new PolyNode();
    PolyNode* curr = dummy;
    PolyNode* p = poly1;  // poly1's pointer
    PolyNode* q = poly2;  // poly2's pointer

    while (p != nullptr && q != nullptr) {
      if (p->power > q->power) {
        curr->next = new PolyNode(p->coefficient, p->power);
        curr = curr->next;
        p = p->next;
      } else if (p->power < q->power) {
        curr->next = new PolyNode(q->coefficient, q->power);
        curr = curr->next;
        q = q->next;
      } else {  // p->power == q->power
        const int sumCoefficient = p->coefficient + q->coefficient;
        if (sumCoefficient != 0) {
          curr->next = new PolyNode(sumCoefficient, p->power);
          curr = curr->next;
        }
        p = p->next;
        q = q->next;
      }
    }

    while (p != nullptr) {
      curr->next = new PolyNode(p->coefficient, p->power);
      curr = curr->next;
      p = p->next;
    }

    while (q != nullptr) {
      curr->next = new PolyNode(q->coefficient, q->power);
      curr = curr->next;
      q = q->next;
    }

    return dummy->next;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for polynomial singly-linked list.
 * class PolyNode {
 *   int coefficient, power;
 *   PolyNode next = null;
 *   PolyNode() {}
 *   PolyNode(int x, int y) { this.coefficient = x; this.power = y; }
 *   PolyNode(int x, int y, PolyNode next) {
 *     this.coefficient = x;
 *     this.power = y;
 *     this.next = next;
 *   }
 * }
 */

class Solution {
  public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
    PolyNode dummy = new PolyNode();
    PolyNode curr = dummy;
    PolyNode p = poly1; // poly1's pointer
    PolyNode q = poly2; // poly2's pointer

    while (p != null && q != null) {
      if (p.power > q.power) {
        curr.next = new PolyNode(p.coefficient, p.power);
        curr = curr.next;
        p = p.next;
      } else if (p.power < q.power) {
        curr.next = new PolyNode(q.coefficient, q.power);
        curr = curr.next;
        q = q.next;
      } else { // p.power == q.power
        final int sumCoefficient = p.coefficient + q.coefficient;
        if (sumCoefficient != 0) {
          curr.next = new PolyNode(sumCoefficient, p.power);
          curr = curr.next;
        }
        p = p.next;
        q = q.next;
      }
    }

    while (p != null) {
      curr.next = new PolyNode(p.coefficient, p.power);
      curr = curr.next;
      p = p.next;
    }

    while (q != null) {
      curr.next = new PolyNode(q.coefficient, q.power);
      curr = curr.next;
      q = q.next;
    }

    return dummy.next;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 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 = PolyNode()
    curr = dummy
    p = poly1  # poly1's pointer
    q = poly2  # poly2's pointer

    while p and q:
      if p.power > q.power:
        curr.next = PolyNode(p.coefficient, p.power)
        curr = curr.next
        p = p.next
      elif p.power < q.power:
        curr.next = PolyNode(q.coefficient, q.power)
        curr = curr.next
        q = q.next
      else:  # p.power == q.power
        sumCoefficient = p.coefficient + q.coefficient
        if sumCoefficient != 0:
          curr.next = PolyNode(sumCoefficient, p.power)
          curr = curr.next
        p = p.next
        q = q.next

    while p:
      curr.next = PolyNode(p.coefficient, p.power)
      curr = curr.next
      p = p.next

    while q:
      curr.next = PolyNode(q.coefficient, q.power)
      curr = curr.next
      q = q.next

    return dummy.next