Solved! Leetcode 2816. Double a Number Represented as a Linked List

Description: Double a Number Represented as a Linked List

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

Example 1

<strong>Input:</strong> head = [1,8,9]
<strong>Output:</strong> [3,7,8]
<strong>Explanation:</strong> The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Input: head = [1,8,9]

Output: [3,7,8]

Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2

<strong>Input:</strong> head = [9,9,9]
<strong>Output:</strong> [1,9,9,8]
<strong>Explanation:</strong> The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998.

Input: head = [9,9,9]

Output: [1,9,9,8]

Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998.

Constraints

The number of nodes in the list is in the range [1, 10⁴]
0 <= Node.val <= 9
The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        if(head==null){
            return head;
        }
        //1. reverse the linkedlist
        ListNode node =  reverse(head);
        ListNode p = node;
        int carry = 0;
        ListNode prev = null;
        //2. double the value of nodes
        while(p!=null){
            int val = p.val*2+carry;
            p.val = val%10;
            carry = val/10;
            prev = p;
            p = p.next;
        }
        //3. add an additional node in case of a carry
        if(carry>0){
            prev.next = new ListNode(carry);
        }
        //4. reverse the resulting linked list
        node = reverse(node);
        return node;
    }

    private void print(ListNode node){
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
    }

    private ListNode reverse(ListNode node){
        ListNode prev = null;
        ListNode curr = node;
        while(curr!=null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

class Solution {

public ListNode doubleIt(ListNode head) {

if(head==null){

return head;

}

//1. reverse the linkedlist

ListNode node = reverse(head);

ListNode p = node;

int carry = 0;

ListNode prev = null;

//2. double the value of nodes

while(p!=null){

int val = p.val*2+carry;

p.val = val%10;

carry = val/10;

prev = p;

p = p.next;

}

//3. add an additional node in case of a carry

if(carry>0){

prev.next = new ListNode(carry);

}

//4. reverse the resulting linked list

node = reverse(node);

return node;

}

private void print(ListNode node){

while(node!=null){

System.out.print(node.val+" ");

node = node.next;

}

private ListNode reverse(ListNode node){

ListNode prev = null;

ListNode curr = node;

while(curr!=null){

ListNode next = curr.next;

curr.next = prev;

prev = curr;

curr = next;

}

return prev;

}

Time Complexity

O(n), where n is the number of nodes in a linked list

Space Complexity

O(1)

Rate this post

Coddicted