Double a Number Represented in a Linked List

Last Updated : 05 Jun, 2024

Given a non-empty linked list representing a non-negative integer without leading zeroes the task is to double the value of whole linked list like(2->3->1 then answer will be 4->6->2) and print the resultant linked list.

Examples:

Input: head = [2, 0, 9]
Output: [4, 1, 8]
Explanation: Given linked list represents the number 209, Hence the returned linked list represents the number 209* 2 = 418.

Input: head = [8, 9, 1]
Output: [1, 7, 8, 2]
Explanation: Given linked list represents the number 891, Hence the returned linked list represents the number 891 * 2 = 1782.

Approach:

To double the value represented as a linked list, firstly we create an empty linked list node with data= 0 and mark it as current. Now, traverse over the linked list and multiply the value at each node with 2. After multiplying if the value exceeds 9, then add one to value in current node. Now create new node and put units place digit of value as data of new Node and add it to list. Make this new node current. After traversing over all the nodes, return head of new list of its value is not zero else return next node of head of new list.

Step by step algorithm:

Store head of linked list in curr .
Create a new Linked list node curr2 with value 0, mark it as head2.
Now traverse through linked list until curr is not equal to nullptr.
At every iteration , do the following
1. multiply data in curr by 2 , create a new node with units place of this value
2. if it exceeds 9 - add 1 to curr node's data
3. add this new node to new list , ie.curr2->next = newNode
4. move curr2 to new Node
Move curr to next node of the given linked list.
After traversing complete list , return head2 if its data is not 0 else return node next to head2.

Below is the code implementation of the above approach:-

C++

#include <iostream>
using namespace std;

// ListNode class representing each node in the linked list
class ListNode {
public:
    int val;
    ListNode* next;
    // Default constructor
    ListNode()
        : val(0)
        , next(nullptr)
    {
    }
    // Constructor with data
    ListNode(int x)
        : val(x)
        , next(nullptr)
    {
    }
    // constructor with data and next node
    ListNode(int x, ListNode* next)
        : val(x)
        , next(next)
    {
    }
};

// Function to double the value of each node in a linked
// list
ListNode* doubleLL(ListNode* head)
{
    ListNode* curr = head;
    // create new linked list
    ListNode* curr2 = new ListNode(0);
    ListNode* head2 = curr2;

    while (curr != nullptr) {
        int num = curr->val;
        // multiply value of current node of list with 2
        num = num * 2;
        // if 2*num is greater than 9 , add 1 to curr2->val
        if (num > 9) {
            // units place digit is value of new Node
            ListNode* newNode = new ListNode(num % 10);
            // if 2*curr->val is more than 9 , then we add 1
            // to curr2->val
            curr2->val += 1;
            // add new Node in the list
            curr2->next = newNode;
            // make new node as current2
            curr2 = curr2->next;
            // if num is not greater than 9 , no need to
            // change curr2.
        }
        else {
            // just create new Node with 2*num and add it to
            // new list, make this node curr2
            ListNode* newNode = new ListNode(num);
            curr2->next = newNode;
            curr2 = curr2->next;
        }
        curr = curr->next;
    }
    // if head2 is empty ie it has value 0 , then we return
    // node next of it
    if (head2->val == 0)
        return head2->next;
    // if head2 is not empty , return it
    return head2;
}

// Main method to test the code
int main()
{
    // Create a linked list with initial value 1
    ListNode* head = new ListNode(2);
    // Add a node with value 8
    ListNode* h1 = new ListNode(0);
    // Connect it to the first node
    head->next = h1;
    // Add a node with value 9
    ListNode* h2 = new ListNode(9);
    // Connect it to the second node
    h1->next = h2;
    // Double the values of the linked list
    ListNode* result = doubleLL(head);
    // Print the values of the resulting linked list
    while (result != nullptr) {
        cout << result->val << " ";
        result = result->next;
    }

    return 0;
}

// This code is contributed by Vaidish Thosar

Java

// ListNode class representing each node in the linked list
class ListNode {
    int val;
    ListNode next;

    // Default constructor
    ListNode() {
        val = 0;
        next = null;
    }

    // Constructor with data
    ListNode(int x) {
        val = x;
        next = null;
    }

    // constructor with data and next node
    ListNode(int x, ListNode next) {
        val = x;
        this.next = next;
    }
}

// Function to double the value of each node in a linked list
class DoubleLinkedList {
    public ListNode doubleLL(ListNode head) {
        ListNode curr = head;
        // create new linked list
        ListNode curr2 = new ListNode(0);
        ListNode head2 = curr2;

        while (curr != null) {
            int num = curr.val;
            // multiply value of current node of list with 2
            num = num * 2;
            // if 2*num is greater than 9 , add 1 to curr2->val
            if (num > 9) {
                // units place digit is value of new Node
                ListNode newNode = new ListNode(num % 10);
                // if 2*curr->val is more than 9 , then we add 1
                // to curr2->val
                curr2.val += 1;
                // add new Node in the list
                curr2.next = newNode;
                // make new node as current2
                curr2 = curr2.next;
                // if num is not greater than 9 , no need to
                // change curr2.
            } else {
                // just create new Node with 2*num and add it to
                // new list, make this node curr2
                ListNode newNode = new ListNode(num);
                curr2.next = newNode;
                curr2 = curr2.next;
            }
            curr = curr.next;
        }
        // if head2 is empty ie it has value 0 , then we return
        // node next of it
        if (head2.val == 0)
            return head2.next;
        // if head2 is not empty , return it
        return head2;
    }

    // Main method to test the code
    public static void main(String[] args) {
        // Create a linked list with initial value 1
        ListNode head = new ListNode(2);
        // Add a node with value 8
        ListNode h1 = new ListNode(0);
        // Connect it to the first node
        head.next = h1;
        // Add a node with value 9
        ListNode h2 = new ListNode(9);
        // Connect it to the second node
        h1.next = h2;
        // Create an instance of DoubleLinkedList class
        DoubleLinkedList dll = new DoubleLinkedList();
        // Double the values of the linked list
        ListNode result = dll.doubleLL(head);
        // Print the values of the resulting linked list
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Python

# ListNode class representing each node in the linked list
class ListNode:
    def __init__(self, x=0):
        self.val = x
        self.next = None

# Function to double the value of each node in a linked list
def double_linked_list(head):
    curr = head
    # create new linked list
    curr2 = ListNode(0)
    head2 = curr2

    while curr:
        num = curr.val
        # multiply value of current node of list with 2
        num *= 2
        # if 2*num is greater than 9, add 1 to curr2->val
        if num > 9:
            # units place digit is value of new Node
            new_node = ListNode(num % 10)
            # if 2*curr->val is more than 9, then we add 1 to curr2->val
            curr2.val += 1
            # add new Node in the list
            curr2.next = new_node
            # make new node as current2
            curr2 = curr2.next
        else:
            # just create new Node with 2*num and add it to new list, make this node curr2
            new_node = ListNode(num)
            curr2.next = new_node
            curr2 = curr2.next
        curr = curr.next

    # if head2 is empty (i.e., it has value 0), then we return node next of it
    if head2.val == 0:
        return head2.next
    # if head2 is not empty, return it
    return head2

# Main method to test the code
if __name__ == "__main__":
    # Create a linked list with initial value 2
    head = ListNode(2)
    # Add a node with value 0
    h1 = ListNode(0)
    # Connect it to the first node
    head.next = h1
    # Add a node with value 9
    h2 = ListNode(9)
    # Connect it to the second node
    h1.next = h2

    # Double the values of the linked list
    result = double_linked_list(head)
    # Print the values of the resulting linked list
    while result:
        print(result.val, end=" ")
        result = result.next

JavaScript

// ListNode class representing each node in the linked list
class ListNode {
    constructor(val = 0) {
        this.val = val;
        this.next = null;
    }
}

// Function to double the value of each node in a linked list
function doubleLinkedList(head) {
    let curr = head;
    // create new linked list
    let curr2 = new ListNode(0);
    let head2 = curr2;

    while (curr !== null) {
        let num = curr.val;
        // multiply value of current node of list with 2
        num *= 2;
        // if 2*num is greater than 9, add 1 to curr2->val
        if (num > 9) {
            // units place digit is value of new Node
            let newNode = new ListNode(num % 10);
            // if 2*curr->val is more than 9, then we add 1 to curr2->val
            curr2.val += 1;
            // add new Node in the list
            curr2.next = newNode;
            // make new node as current2
            curr2 = curr2.next;
        } else {
            // just create new Node with 2*num and add it to new list, make this node curr2
            let newNode = new ListNode(num);
            curr2.next = newNode;
            curr2 = curr2.next;
        }
        curr = curr.next;
    }

    // if head2 is empty (i.e., it has value 0), then we return node next of it
    if (head2.val === 0) {
        return head2.next;
    }
    // if head2 is not empty, return it
    return head2;
}

// Main method to test the code
function main() {
    // Create a linked list with initial value 2
    let head = new ListNode(2);
    // Add a node with value 0
    let h1 = new ListNode(0);
    // Connect it to the first node
    head.next = h1;
    // Add a node with value 9
    let h2 = new ListNode(9);
    // Connect it to the second node
    h1.next = h2;

    // Double the values of the linked list
    let result = doubleLinkedList(head);
    // Print the values of the resulting linked list
    while (result !== null) {
        console.log(result.val);
        result = result.next;
    }
}

// Call the main function
main();