Implement a function to find the sum of two linked lists

problemsolving

Adding two numbers represented as linked lists is a classic interview problem that tests your understanding of linked lists and fundamental arithmetic

Published

September 5, 2024

Adding two numbers represented as linked lists is a classic interview problem that tests your understanding of linked lists and fundamental arithmetic. This post will walk you through how to implement a JavaScript function to achieve this efficiently. We’ll handle cases with varying list lengths and consider the potential for carrying over digits.

First, let’s define a simple Node class to represent elements in our linked lists:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Now, let’s create the function sumLists that takes two linked lists as input and returns a new linked list representing their sum:

function sumLists(l1, l2) {
  let dummyHead = new Node(0); // Dummy node to simplify handling of the result
  let current = dummyHead;
  let carry = 0;

  while (l1 || l2 || carry) { // Continue until both lists are exhausted and there's no carry
    let sum = carry;
    if (l1) {
      sum += l1.data;
      l1 = l1.next;
    }
    if (l2) {
      sum += l2.data;
      l2 = l2.next;
    }

    carry = Math.floor(sum / 10); // Calculate the carry
    current.next = new Node(sum % 10); // Add the remainder to the result list
    current = current.next;
  }

  return dummyHead.next; // Return the actual result list, excluding the dummy head
}

Let’s break down the code:

dummyHead: We use a dummy node to simplify adding nodes to the beginning of the result list. This avoids special handling for the first node.
while loop: The loop continues as long as either list has remaining nodes or there’s a carry from the previous addition.
sum calculation: The sum variable accumulates the digits from both lists (if present) and the carry from the previous iteration.
carry calculation: Integer division (Math.floor(sum / 10)) determines the carry-over digit.
Node creation: The remainder (sum % 10) is added as data to a new node and appended to the result list.

Example Usage:

Let’s create two sample linked lists:

// 617 (7 -> 1 -> 6)
const l1 = new Node(7);
l1.next = new Node(1);
l1.next.next = new Node(6);

// 295 (5 -> 9 -> 2)
const l2 = new Node(5);
l2.next.next = new Node(9);
l2.next = new Node(2);


const sumList = sumLists(l1, l2);

// Output the sum list (912)
let resultString = "";
let currentNode = sumList;
while (currentNode){
  resultString += currentNode.data;
  currentNode = currentNode.next;
}
console.log(resultString); // Output: 912

This example demonstrates how the function correctly handles addition, including the carry-over. Remember to modify the output method to your specific needs; this example simply concatenates the digits for display. This approach offers a clear, efficient solution to this common linked list problem. You can easily extend this to handle negative numbers or different number systems with minor modifications.

Built by the author of this blog — Jovis AI automates project management so your engineering team can focus on building. Try it free →