Write a function that takes a singly linked list and returns a complete copy of that list.
Practice this problem
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:
|
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // 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)); // set the `.next` pointer of the new node to point to the current // first node of the list. // change the head pointer to point to the new node, so it is // now the first node in the list. // 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 // special case for the first new node newList = (struct Node*)malloc(sizeof(struct Node)); newList->data = current->data; tail->next = (struct Node*)malloc(sizeof(struct Node)); tail->data = current->data; 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--) { struct Node* dup = copyList(head); // print duplicate linked list |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> NULL
|
Node(int data, Node next) // Helper function to print a given linked list public static void printList(Node head) System.out.print(ptr.data + " —> "); 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 // special case for the first new node newList = new Node(current.data, null); tail.data = current.data; public static void main(String[] args) int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); Node copy = copyList(head); // print duplicate linked list |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> null
|
def __init__(self, data=None, next=None): # Helper function to print a given linked list print(ptr.data, end=' —> ') # Function takes a linked list and returns its complete copy 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 # special case for the first new node newList = Node(current.data, None) if __name__ == '__main__': # construct a linked list for i in reversed(range(4)): # print duplicate linked list |
Download Run Code
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.
|
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // 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)); // set the `.next` pointer of the new node to point to the current // first node of the list. // change the head pointer to point to the new node, so it is // now the first node in the list. // 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 // special case for the first new node push(&newList, current->data); push(&(tail->next), current->data); // add each node at the tail tail = tail->next; // advance the tail to the new last node 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--) { struct Node* dup = copyList(head); // print duplicate linked list |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> NULL
|
Node(int data, Node next) // Helper function to print a given linked list public static void printList(Node head) System.out.print(ptr.data + " —> "); 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 // special case for the first new node newList = new Node(current.data, newList); // add each node at the tail tail.next = new Node(current.data, tail.next); // advance the tail to the new last node public static void main(String[] args) int[] keys = {1, 2, 3, 4}; // points to the head node of the linked list // construct a linked list for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); Node dup = copyList(head); // print duplicate linked list |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> null
|
def __init__(self, data=None, next=None): # Helper function to print a given linked list print(ptr.data, end=' —> ') # Function takes a linked list and returns a complete copy of that # list using a dummy node using the `push()` function 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 # special case for the first node newList = Node(current.data, newList) tail.next = Node(current.data, tail.next) # add each node at the tail tail = tail.next # advance the tail to the new last node if __name__ == '__main__': # construct a linked list for i in reversed(range(4)): # print duplicate linked list |
Download Run Code
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:
|
// Helper function to print a given linked list void printList(struct Node* head) printf("%d —> ", ptr->data); // 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)); // set the `.next` pointer of the new node to point to the current // first node of the list. // change the head pointer to point to the new node, so it is // now the first node in the list. // 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 tail = &dummy; // start the tail pointing at the dummy push(&(tail->next), current->data); // add each node at the tail tail = tail->next; // advance the tail to the new last node 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--) { struct Node* dup = copyList(head); // print duplicate linked list |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> NULL
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); } } |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> null
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) |
Download Run Code
Output:
1 —> 2 —> 3 —> 4 —> None
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.
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
|