How do you convert a number to a linked list in Python?

Add 1 to a number represented as linked list

Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)

Table of Contents Show

• Add 1 to a number represented as linked list
• The challenge
• Program to convert Linked list representing binary number to decimal integer in Python
• “how to convert linked list to list in python” Code Answer
• Python answers related to “how to convert linked list to list in python”
• Python queries related to “how to convert linked list to list in python”

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Below are the steps :

1. Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.
2. Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.
3. Reverse modified linked list and return head.

Below is the implementation of above steps.

C++

// C++ program to add 1 to a linked list #include <bits/stdc++.h> using namespace std; /* Linked list node */ class Node { public: int data; Node* next; }; /* Function to create a new node with given data */ Node *newNode(int data) { Node *new_node = new Node; new_node->data = data; new_node->next = NULL; return new_node; } /* Function to reverse the linked list */ Node *reverse(Node *head) { Node * prev = NULL; Node * current = head; Node * next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */ Node *addOneUtil(Node *head) { // res is head node of the resultant list Node* res = head; Node *temp; int carry = 1, sum; while (head != NULL) //while both lists exist { // Calculate value of next digit in resultant list. // The next digit is sum of following things // (i) Carry // (ii) Next digit of head list (if there is a // next digit) sum = carry + head->data; // update carry for next calculation carry = (sum >= 10)? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head->data = sum; // Move head and second pointers to next nodes temp = head; head = head->next; } // if some carry is still there, add a new node to // result list. if (carry > 0) temp->next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). Node* addOne(Node *head) { // Reverse linked list head = reverse(head); // Add one from left to right of reversed // list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a linked list void printList(Node *node) { while (node != NULL) { cout << node->data; node = node->next; } cout<<endl; } /* Driver program to test above function */ int main(void) { Node *head = newNode(1); head->next = newNode(9); head->next->next = newNode(9); head->next->next->next = newNode(9); cout << "List is "; printList(head); head = addOne(head); cout << "\nResultant list is "; printList(head); return 0; } // This is code is contributed by rathbhupendra

C

// C program to add 1 to a linked list #include<bits/stdc++.h> /* Linked list node */ struct Node { int data; Node* next; }; /* Function to create a new node with given data */ Node *newNode(int data) { Node *new_node = new Node; new_node->data = data; new_node->next = NULL; return new_node; } /* Function to reverse the linked list */ Node *reverse(Node *head) { Node * prev = NULL; Node * current = head; Node * next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */ Node *addOneUtil(Node *head) { // res is head node of the resultant list Node* res = head; Node *temp, *prev = NULL; int carry = 1, sum; while (head != NULL) //while both lists exist { // Calculate value of next digit in resultant list. // The next digit is sum of following things // (i) Carry // (ii) Next digit of head list (if there is a // next digit) sum = carry + head->data; // update carry for next calculation carry = (sum >= 10)? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head->data = sum; // Move head and second pointers to next nodes temp = head; head = head->next; } // if some carry is still there, add a new node to // result list. if (carry > 0) temp->next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). Node* addOne(Node *head) { // Reverse linked list head = reverse(head); // Add one from left to right of reversed // list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a linked list void printList(Node *node) { while (node != NULL) { printf("%d", node->data); node = node->next; } printf("\n"); } /* Driver program to test above function */ int main(void) { Node *head = newNode(1); head->next = newNode(9); head->next->next = newNode(9); head->next->next->next = newNode(9); printf("List is "); printList(head); head = addOne(head); printf("\nResultant list is "); printList(head); return 0; }

Java

// Java program to add 1 to a linked list class GfG { /* Linked list node */ static class Node { int data; Node next; } /* Function to create a new node with given data */ static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } /* Function to reverse the linked list */ static Node reverse(Node head) { Node prev = null; Node current = head; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */ static Node addOneUtil(Node head) { // res is head node of the resultant list Node res = head; Node temp = null, prev = null; int carry = 1, sum; while (head != null) // while both lists exist { // Calculate value of next digit in resultant // list. The next digit is sum of following // things (i) Carry (ii) Next digit of head list // (if there is a next digit) sum = carry + head.data; // update carry for next calculation carry = (sum >= 10) ? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head.data = sum; // Move head and second pointers to next nodes temp = head; head = head.next; } // if some carry is still there, add a new node to // result list. if (carry > 0) temp.next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). static Node addOne(Node head) { // Reverse linked list head = reverse(head); // Add one from left to right of reversed // list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } System.out.println(); } /* Driver code */ public static void main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print("Resultant list is "); printList(head); } } // This code is contributed by prerna saini

Python3

# Python3 program to add 1 to a linked list import sys import math # Linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to create a new node with given data */ def newNode(data): return Node(data) # Function to reverse the linked list */ def reverseList(head): if not head: return curNode = head prevNode = head nextNode = head.next curNode.next = None while(nextNode): curNode = nextNode nextNode = nextNode.next curNode.next = prevNode prevNode = curNode return curNode # Adds one to a linked lists and return the head # node of resultant list def addOne(head): # Reverse linked list and add one to head head = reverseList(head) k = head carry = 0 prev = None head.data += 1 # update carry for next calculation while(head != None) and (head.data > 9 or carry > 0): prev = head head.data += carry carry = head.data // 10 head.data = head.data % 10 head = head.next if carry > 0: prev.next = Node(carry) # Reverse the modified list return reverseList(k) # A utility function to print a linked list def printList(head): if not head: return while(head): print("{}".format(head.data), end="") head = head.next # Driver code if __name__ == '__main__': head = newNode(1) head.next = newNode(9) head.next.next = newNode(9) head.next.next.next = newNode(9) print("List is: ", end="") printList(head) head = addOne(head) print("\nResultant list is: ", end="") printList(head) # This code is contributed by Rohit

C#

// C# program to add 1 to a linked list using System; class GfG { /* Linked list node */ public class Node { public int data; public Node next; } /* Function to create a new node with given data */ static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } /* Function to reverse the linked list */ static Node reverse(Node head) { Node prev = null; Node current = head; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */ static Node addOneUtil(Node head) { // res is head node of the resultant list Node res = head; Node temp = null, prev = null; int carry = 1, sum; while (head != null) // while both lists exist { // Calculate value of next digit in resultant // list. The next digit is sum of following // things (i) Carry (ii) Next digit of head list // (if there is a next digit) sum = carry + head.data; // update carry for next calculation carry = (sum >= 10) ? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head.data = sum; // Move head and second pointers to next nodes temp = head; head = head.next; } // if some carry is still there, add a new node to // result list. if (carry > 0) temp.next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). static Node addOne(Node head) { // Reverse linked list head = reverse(head); // Add one from left to right of reversed // list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a linked list static void printList(Node node) { while (node != null) { Console.Write(node.data); node = node.next; } Console.WriteLine(); } /* Driver code */ public static void Main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); Console.Write("List is "); printList(head); head = addOne(head); Console.WriteLine(); Console.Write("Resultant list is "); printList(head); } } // This code contributed by Rajput-Ji

Javascript

<script> // Javascript program to add 1 to a linked list /* Linked list node */ class Node { constructor() { this.data = 0; this.next = null; } }; /* Function to create a new node with given data */ function newNode(data) { var new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } /* Function to reverse the linked list */ function reverse(head) { var prev = null; var current = head; var next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } /* Adds one to a linked lists and return the head node of resultant list */ function addOneUtil(head) { // res is head node of the resultant list var res = head; var temp, prev = null; var carry = 1, sum; while (head != null) //while both lists exist { // Calculate value of next digit in resultant list. // The next digit is sum of following things // (i) Carry // (ii) Next digit of head list (if there is a // next digit) sum = carry + head.data; // update carry for next calculation carry = (sum >= 10)? 1 : 0; // update sum if it is greater than 10 sum = sum % 10; // Create a new node with sum as data head.data = sum; // Move head and second pointers to next nodes temp = head; head = head.next; } // if some carry is still there, add a new node to // result list. if (carry > 0) temp.next = newNode(carry); // return head of the resultant list return res; } // This function mainly uses addOneUtil(). function addOne(head) { // Reverse linked list head = reverse(head); // Add one from left to right of reversed // list head = addOneUtil(head); // Reverse the modified list return reverse(head); } // A utility function to print a linked list function printList(node) { while (node != null) { document.write( node.data); node = node.next; } document.write("<br>"); } /* Driver program to test above function */ var head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); document.write( "List is "); printList(head); head = addOne(head); document.write( "<br>Resultant list is "); printList(head); // This code is contributed by rrrtnx. </script>

Output List is 1999 Resultant list is 2000

Recursive Implementation:
We can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.

Below is the implementation of recursive solution.

C++

// Recursive C++ program to add 1 to a linked list #include <bits/stdc++.h> /* Linked list node */ struct Node { int data; Node* next; }; /* Function to create a new node with given data */ Node* newNode(int data) { Node* new_node = new Node; new_node->data = data; new_node->next = NULL; return new_node; } // Recursively add 1 from end to beginning and returns // carry after all nodes are processed. int addWithCarry(Node* head) { // If linked list is empty, then // return carry if (head == NULL) return 1; // Add carry returned be next node call int res = head->data + addWithCarry(head->next); // Update data and return new carry head->data = (res) % 10; return (res) / 10; } // This function mainly uses addWithCarry(). Node* addOne(Node* head) { // Add 1 to linked list from end to beginning int carry = addWithCarry(head); // If there is carry after processing all nodes, // then we need to add a new node to linked list if (carry) { Node* newNode = new Node; newNode->data = carry; newNode->next = head; return newNode; // New node becomes head now } return head; } // A utility function to print a linked list void printList(Node* node) { while (node != NULL) { printf("%d", node->data); node = node->next; } printf("\n"); } /* Driver code */ int main(void) { Node* head = newNode(1); head->next = newNode(9); head->next->next = newNode(9); head->next->next->next = newNode(9); printf("List is "); printList(head); head = addOne(head); printf("\nResultant list is "); printList(head); return 0; }

Java

// Recursive Java program to add 1 to a linked list class GfG { /* Linked list node */ static class Node { int data; Node next; } /* Function to create a new node with given data */ static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } // Recursively add 1 from end to beginning and returns // carry after all nodes are processed. static int addWithCarry(Node head) { // If linked list is empty, then // return carry if (head == null) return 1; // Add carry returned be next node call int res = head.data + addWithCarry(head.next); // Update data and return new carry head.data = (res) % 10; return (res) / 10; } // This function mainly uses addWithCarry(). static Node addOne(Node head) { // Add 1 to linked list from end to beginning int carry = addWithCarry(head); // If there is carry after processing all nodes, // then we need to add a new node to linked list if (carry > 0) { Node newNode = newNode(carry); newNode.next = head; return newNode; // New node becomes head now } return head; } // A utility function to print a linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } System.out.println(); } /* Driver code */ public static void main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print("Resultant list is "); printList(head); } } // This code is contributed by shubham96301

Python

# Recursive Python program to add 1 to a linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None # Function to create a new node with given data def newNode(data): new_node = Node(0) new_node.data = data new_node.next = None return new_node # Recursively add 1 from end to beginning and returns # carry after all nodes are processed. def addWithCarry(head): # If linked list is empty, then # return carry if (head == None): return 1 # Add carry returned be next node call res = head.data + addWithCarry(head.next) # Update data and return new carry head.data = int((res) % 10) return int((res) / 10) # This function mainly uses addWithCarry(). def addOne(head): # Add 1 to linked list from end to beginning carry = addWithCarry(head) # If there is carry after processing all nodes, # then we need to add a new node to linked list if (carry != 0): newNode = Node(0) newNode.data = carry newNode.next = head return newNode # New node becomes head now return head # A utility function to print a linked list def printList(node): while (node != None): print( node.data,end = "") node = node.next print("\n") # Driver program to test above function head = newNode(1) head.next = newNode(9) head.next.next = newNode(9) head.next.next.next = newNode(9) print("List is ") printList(head) head = addOne(head) print("\nResultant list is ") printList(head) # This code is contributed by Arnab Kundu

C#

// Recursive C# program to add 1 to a linked list using System; class GfG { /* Linked list node */ public class Node { public int data; public Node next; } /* Function to create a new node with given data */ public static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } // Recursively add 1 from end to beginning and returns // carry after all nodes are processed. public static int addWithCarry(Node head) { // If linked list is empty, then // return carry if (head == null) return 1; // Add carry returned be next node call int res = head.data + addWithCarry(head.next); // Update data and return new carry head.data = (res) % 10; return (res) / 10; } // This function mainly uses addWithCarry(). public static Node addOne(Node head) { // Add 1 to linked list from end to beginning int carry = addWithCarry(head); Node newNodes = null; // If there is carry after processing all nodes, // then we need to add a new node to linked list if (carry > 0) { newNodes = newNode(carry); newNodes.next = head; return newNodes; // New node becomes head now } return head; } // A utility function to print a linked list public static void printList(Node node) { while (node != null) { Console.Write(node.data); node = node.next; } Console.WriteLine(); } /* Driver code */ public static void Main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); Console.Write("List is "); printList(head); head = addOne(head); Console.WriteLine(); Console.Write("Resultant list is "); printList(head); } } /* This code contributed by PrinciRaj1992 */

Javascript

<script> // Recursive JavaScript program // to add 1 to a linked list /* Linked list node */ class Node { constructor() { this.data = 0; this.next = null; } } /* Function to create a new node with given data */ function newNode(data) { var new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } // Recursively add 1 from end to beginning and returns // carry after all nodes are processed. function addWithCarry(head) { // If linked list is empty, then // return carry if (head == null) return 1; // Add carry returned be next node call var res = head.data + addWithCarry(head.next); // Update data and return new carry head.data = res % 10; return parseInt(res / 10); } // This function mainly uses addWithCarry(). function addOne(head) { // Add 1 to linked list from end to beginning var carry = addWithCarry(head); var newNodes = null; // If there is carry after processing all nodes, // then we need to add a new node to linked list if (carry > 0) { newNodes = newNode(carry); newNodes.next = head; return newNodes; // New node becomes head now } return head; } // A utility function to print a linked list function printList(node) { while (node != null) { document.write(node.data); node = node.next; } document.write("<br>"); } /* Driver code */ var head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); document.write("List is "); printList(head); head = addOne(head); document.write("<br>"); document.write("Resultant list is "); printList(head); </script>

Output List is 1999 Resultant list is 2000

Simple approach and easy implementation: The idea is to store the last non 9 digit pointer so that if the last pointer is zero we can replace all the nodes after stored node(which contains the location of last digit before 9) to 0 and add the value of the stored node by 1

C++

// Recursive C++ program to add 1 to a linked list #include <bits/stdc++.h> /* Linked list node */ struct Node { int data; Node* next; }; /* Function to create a new node with given data */ Node* newNode(int data) { Node* new_node = new Node; new_node->data = data; new_node->next = NULL; return new_node; } Node* addOne(Node* head) { // Your Code here // return head of list after adding one Node* ln = head; if (head->next == NULL) { head->data += 1; return head; } Node* t = head; int prev; while (t->next) { if (t->data != 9) { ln = t; } t = t->next; } if (t->data == 9 && ln != NULL) { if (ln->data == 9 && ln == head) { Node* temp = newNode(1); temp->next = head; head = temp; t = ln; } else { t = ln; t->data += 1; t = t->next; } while (t) { t->data = 0; t = t->next; } } else { t->data += 1; } return head; } // A utility function to print a linked list void printList(Node* node) { while (node != NULL) { printf("%d->", node->data); node = node->next; } printf("NULL"); printf("\n"); } /* Driver code */ int main(void) { Node* head = newNode(1); head->next = newNode(9); head->next->next = newNode(9); head->next->next->next = newNode(9); printf("List is "); printList(head); head = addOne(head); printf("\nResultant list is "); printList(head); return 0; } // This code is contribute bu maddler

Java

// Recursive Java program to add 1 to a linked list class GFG{ // Linked list node static class Node { int data; Node next; } // Function to create a new node with given data static Node newNode(int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null; return new_node; } static Node addOne(Node head) { // Return head of list after adding one Node ln = head; if (head.next == null) { head.data += 1; return head; } Node t = head; int prev; while (t.next != null) { if (t.data != 9) { ln = t; } t = t.next; } if (t.data == 9 && ln != null) { t = ln; t.data += 1; t = t.next; while (t != null) { t.data = 0; t = t.next; } } else { t.data += 1; } return head; } // A utility function to print a linked list static void printList(Node node) { while (node != null) { System.out.print(node.data); node = node.next; } System.out.println(); } // Driver code public static void main(String[] args) { Node head = newNode(1); head.next = newNode(9); head.next.next = newNode(9); head.next.next.next = newNode(9); System.out.print("List is "); printList(head); head = addOne(head); System.out.println(); System.out.print("Resultant list is "); printList(head); } } // This code is contributed by rajsanghavi9.

Output List is 1999 Resultant list is 2000

This article is contributed by Aditya Goel. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Article Tags :

Linked List

Amazon

Practice Tags :

Amazon

Linked List

The challenge

Preloaded for you is a class, struct, or derived data typeNode(depending on the language) used to construct linked lists in this challenge:

Create a functionstringifywhich accepts an argumentlist/$listand returns a string representation of the list. The string representation of the list starts with the value of the currentNode, specified by itsdata/$data/Dataproperty, followed by a whitespace character, an arrow, and another whitespace character (" -> "), followed by the rest of the list. The end of the string representation of a list must always end withNone. For example, given the following list:

… its string representation would be:

And given the following linked list:

… its string representation would be:

Note thatNoneitself is also considered a valid linked list. In that case, its string representation would simply be"None"(again, depending on the language).

Program to convert Linked list representing binary number to decimal integer in Python

Suppose we have a singly linked list. the linked list is representing a binary number with most significant digits first, we have to return it as decimal number.

So, if the input is like [1,0,1,1,0], then the output will be 22

To solve this, we will follow these steps −

• l := a new list
• while node is not null, do
  • insert value of node at the end of l
  • node:= next of node
• k := 0, v:= 0
• for i in range size of l - 1 to 0, decrease by 1, do
  • if l[i] is same as 1, then
    • v := v + 2^k
  • k := k + 1
• return v

Let us see the following implementation to get better understanding −

“how to convert linked list to list in python” Code Answer

how to convert linked list to list in python

python by wolf-like_hunter

on Jun 02 2021 Comment

0

Source: www.google.com

Python answers related to “how to convert linked list to list in python”

• convert generator to list python
• python reverse linked list
• append method linked list python

• circular linked list in python
• convert list of list to list python
• converting an array to linked List

• python convert array to linked list
• python turn list of lists into list
• make linked list in python

Python queries related to “how to convert linked list to list in python”

• list to linked list python
• convert list to linked list python
• linked list to string python
• linked list to list python
• convert a array to linked list in python
• python create linked list from array
• how to convert a linked list into list python
• convert array to a linked list in python
• python convert linked list to array
• how to convert a list into linked llistin python
• convert array of list to linked list pyhton
• convert a linkedlist to list python
• converting list to linked list python

• how to convert linked list to list in python
• convert linked list to list python
• how to convert list to linked list in python
• turn list into linked list python
• convert list to linkedlist python
• convert list to linked list pythpn
• python convert list into linkedlist
• convert list to list linkedin
• convert list into linked list
• how to turn a linked list into a list in python
• how to convert a list to a linked list python
• converting a list to linked list in python
• python list to linked list

• convert linked list to array python
• python convert array to linked list
• how to convert a linked list to a list in python
• how to convert linked list to a normal list in python
• list to linkedlist python
• convert list in linked list python
• convert linked list into python list
• linked list to list
• how to change a list to a linked list in python
• convert a list to linked list
• convert a linked list to a list python
• python linked list to array
• convert from a list to a linked list