Clone a Linked List
Write a function that takes a singly linked list and returns a complete copy of that list.
1. Naive Approach
The idea is to iterate over the original list in the usual way and maintain two pointers to keep track of the new list: one head pointer and one tail pointer, which always points to the last node of the new list. The first node is done as a special case, and then the tail pointer is used in the standard way for the others.
This approach is demonstrated below in C, Java, and Python:
C
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function takes a linked list and returns its complete copy struct Node* copyList(struct Node* head) { struct Node* current = head; // used to iterate over the original list struct Node* newList = NULL; // head of the new list struct Node* tail = NULL; // point to the last node in a new list while (current != NULL) { // special case for the first new node if (newList == NULL) { newList = (struct Node*)malloc(sizeof(struct Node)); newList->data = current->data; newList->next = NULL; tail = newList; } else { tail->next = (struct Node*)malloc(sizeof(struct Node)); tail = tail->next; tail->data = current->data; tail->next = NULL; } current = current->next; } return newList; } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { push(&head, keys[i]); } // copy linked list struct Node* dup = copyList(head); // print duplicate linked list printList(dup); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node() {} } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Function takes a linked list and returns its complete copy public static Node copyList(Node head) { Node current = head; // used to iterate over the original list Node newList = null; // head of the new list Node tail = null; // point to the last node in a new list while (current != null) { // special case for the first new node if (newList == null) { newList = new Node(current.data, null); tail = newList; } else { tail.next = new Node(); tail = tail.next; tail.data = current.data; tail.next = null; } current = current.next; } return newList; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } // copy linked list Node copy = copyList(head); // print duplicate linked list printList(copy); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function takes a linked list and returns its complete copy def copyList(head): current = head # used to iterate over the original list newList = None # head of the new list tail = None # point to the last node in a new list while current: # special case for the first new node if newList is None: newList = Node(current.data, None) tail = newList else: tail.next = Node() tail = tail.next tail.data = current.data tail.next = None current = current.next return newList if __name__ == '__main__': # construct a linked list head = None for i in reversed(range(4)): head = Node(i + 1, head) # copy linked list copy = copyList(head) # print duplicate linked list printList(copy) |
Output:
1 —> 2 —> 3 —> 4 —> None
2. Using push() function
The above implementation is a little unsatisfying because the 3–step link-in is repeated – once for the first node and once for all the other nodes. The following C, Java, and Python implementation uses push() to allocate and insert the new nodes and avoid repeating that code.
C
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function takes a linked list and returns a complete copy of that // list using a dummy node using the `push()` function struct Node* copyList(struct Node* head) { struct Node* current = head; // used to iterate over the original list struct Node* newList = NULL; // head of the new list struct Node* tail = NULL; // point to the last node in a new list while (current != NULL) { // special case for the first new node if (newList == NULL) { push(&newList, current->data); tail = newList; } else { push(&(tail->next), current->data); // add each node at the tail tail = tail->next; // advance the tail to the new last node } current = current->next; } return newList; } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { push(&head, keys[i]); } // copy linked list struct Node* dup = copyList(head); // print duplicate linked list printList(dup); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Function takes a linked list and returns a complete copy of that // list using a dummy node using the `push()` function public static Node copyList(Node head) { Node current = head; // used to iterate over the original list Node newList = null; // head of the new list Node tail = null; // point to the last node in a new list while (current != null) { // special case for the first new node if (newList == null) { newList = new Node(current.data, newList); tail = newList; } else { // add each node at the tail tail.next = new Node(current.data, tail.next); // advance the tail to the new last node tail = tail.next; } current = current.next; } return newList; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } // copy linked list Node dup = copyList(head); // print duplicate linked list printList(dup); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function takes a linked list and returns a complete copy of that # list using a dummy node using the `push()` function def copyList(head): current = head # used to iterate over the original list newList = None # head of the list tail = None # point to the last node in a new list while current: # special case for the first node if newList is None: newList = Node(current.data, newList) tail = newList else: tail.next = Node(current.data, tail.next) # add each node at the tail tail = tail.next # advance the tail to the new last node current = current.next return newList if __name__ == '__main__': # construct a linked list head = None for i in reversed(range(4)): head = Node(i + 1, head) # copy linked list dup = copyList(head) # print duplicate linked list printList(dup) |
Output:
1 —> 2 —> 3 —> 4 —> None
3. Using Dummy Node
Another strategy is to use a temporary dummy node to take care of the first node case. The dummy node is temporarily the first node in the list, and the tail pointer starts off pointing to it. All nodes are added off the tail pointer.
Following is the C, Java, and Python implementation of the idea:
C
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function takes a linked list and returns a complete copy of that // list using a dummy node struct Node* copyList(struct Node* head) { struct Node* current = head; // used to iterate over the original list struct Node* tail; // point to the last node in the new list struct Node dummy; // build the new list of this dummy node dummy.next = NULL; tail = &dummy; // start the tail pointing at the dummy while (current != NULL) { push(&(tail->next), current->data); // add each node at the tail tail = tail->next; // advance the tail to the new last node current = current->next; } return dummy.next; } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { push(&head, keys[i]); } // copy linked list struct Node* dup = copyList(head); // print duplicate linked list printList(dup); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node() {} } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Function takes a linked list and returns a complete copy of that // list using a dummy node public static Node copyList(Node head) { Node current = head; // used to iterate over the original list Node tail; // point to the last node in the new list Node dummy = new Node(); // build the new list of this dummy node tail = dummy; // start the tail pointing at the dummy while (current != null) { // add each node at the tail tail.next = new Node(current.data, tail.next); // advance the tail to the new last node tail = tail.next; current = current.next; } return dummy.next; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } // copy linked list Node dup = copyList(head); // print duplicate linked list printList(dup); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Function takes a linked list and returns a complete copy of that # list using a dummy node def copyList(head): current = head # used to iterate over the original list dummy = Node() # build the new list of this dummy node # point to the last node in a new list tail = dummy # start the tail pointing at the dummy while current: tail.next = Node(current.data, tail.next) # add each node at the tail tail = tail.next # advance the tail to the new last node current = current.next return dummy.next if __name__ == '__main__': # construct a linked list head = None for i in reversed(range(4)): head = Node(i + 1, head) # copy linked list dup = copyList(head) # print duplicate linked list printList(dup) |
Output:
1 —> 2 —> 3 —> 4 —> None
4. Using Local References
The final and most unusual version uses the “local references” strategy instead of a tail pointer. The strategy is to keep a lastPtr that points to the last pointer in the list. All node additions are made at the lastPtr, and it always points to the last pointer in the list. When the list is empty, it points to the head pointer itself. Later it points to the .next pointer inside the last node in the list.
The implementation can be seen below in C:
C
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Function takes a linked list and returns a complete copy of that // list using local references struct Node* copyList(struct Node* head) { struct Node* current = head; // used to iterate over the original list struct Node* newList = NULL; struct Node** lastPtr; lastPtr = &newList; // start off pointing to the head itself while (current != NULL) { push(lastPtr, current->data); // add each node at `lastPtr` lastPtr = &((*lastPtr)->next); // advance `lastPtr` current = current->next; } return newList; } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { push(&head, keys[i]); } // copy linked list struct Node* dup = copyList(head); // print duplicate linked list printList(dup); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
5. Recursive Solution
Finally, for completeness, following is the recursive version of copyList() in C, Java, and Python. It has the pleasing shortness that recursive code often has. However, it is probably not good for production code since it uses stack space proportional to its list length.
C
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { // allocate a new node in a heap and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; // set the `.next` pointer of the new node to point to the current // first node of the list. newNode->next = *head; // change the head pointer to point to the new node, so it is // now the first node in the list. *head = newNode; } // Recursive function that takes a linked list and returns a complete // copy of that list struct Node* copyList(struct Node* head) { if (head == NULL) { return NULL; } else { // allocate a new node in a heap using `malloc()` and set its data struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = head->data; // recursively set the `.next` pointer of the new node by recurring // for the rest nodes newNode->next = copyList(head->next); return newNode; } } int main(void) { // input keys int keys[] = {1, 2, 3, 4}; int n = sizeof(keys)/sizeof(keys[0]); // points to the head node of the linked list struct Node* head = NULL; // construct a linked list for (int i = n-1; i >= 0; i--) { push(&head, keys[i]); } // copy linked list struct Node* dup = copyList(head); // print duplicate linked list printList(dup); return 0; } |
Output:
1 —> 2 —> 3 —> 4 —> NULL
Java
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node(int data) { this(data, null); } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Recursive function that takes a linked list and returns a complete // copy of that list public static Node copyList(Node head) { if (head == null) { return null; } // allocate a new node in a heap and set its data Node newNode = new Node(head.data); // recursively set the next field of the new node by recurring // for the rest nodes newNode.next = copyList(head.next); return newNode; } public static void main(String[] args) { // input keys int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list Node head = null; // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } // copy linked list Node dup = copyList(head); // print duplicate linked list printList(dup); } } |
Output:
1 —> 2 —> 3 —> 4 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Recursive function that takes a linked list and returns a complete # copy of that list def copyList(head): if head is None: return None # allocate the node and set its data newNode = Node(head.data) # recursively set the `.next` pointer of the new node by recurring # for the rest nodes newNode.next = copyList(head.next) return newNode if __name__ == '__main__': # construct a linked list head = None for i in reversed(range(4)): head = Node(i + 1, head) # copy linked list dup = copyList(head) # print duplicate linked list printList(dup) |
Output:
1 —> 2 —> 3 —> 4 —> None
Source: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
Also See:
Rearrange linked list in increasing order (Sort linked list)
Insert a node to its correct sorted position in a sorted linked list
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)