.jpg)
Copy a Linked List
Problem
Given the head of a Singly Linked List, create a deep copy (duplicate) of the list and return the head of the new copied list.
Deep copy means:
- New nodes must be created
- Copied list should not share memory with original list
- Changes in one list should not affect the other
Example
Original List
10 → 20 → 30 → 40
Copied List
10 → 20 → 30 → 40
(Both lists are separate in memory)
Approach 1 — Iterative Copy Using Traversal
Idea
Traverse the original list and create new nodes one by one, linking them to form the copied list.
Steps
- If head is NULL → return NULL
- Create new head node with same data as original head
- Maintain two pointers:
- currOriginal → original list
- currCopy → copied list
- Traverse original list
- For each node:
- Create new node
- Attach to copied list
- Return new head
Time Complexity
O(N)
Space Complexity
O(N)
(for new nodes)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* copyList(struct Node* head) {
if (head == NULL)
return NULL;
struct Node* newHead = (struct Node*)malloc(sizeof(struct Node));
newHead->data = head->data;
newHead->next = NULL;
struct Node* currOriginal = head->next;
struct Node* currCopy = newHead;
while (currOriginal != NULL) {
currCopy->next = (struct Node*)malloc(sizeof(struct Node));
currCopy = currCopy->next;
currCopy->data = currOriginal->data;
currCopy->next = NULL;
currOriginal = currOriginal->next;
}
return newHead;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
struct Node* copied = copyList(head);
printList(copied);
return 0;
}Output
10 20 30C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
Node* copyList(Node* head) {
if (head == NULL)
return NULL;
Node* newHead = new Node(head->data);
Node* currOriginal = head->next;
Node* currCopy = newHead;
while (currOriginal != NULL) {
currCopy->next = new Node(currOriginal->data);
currCopy = currCopy->next;
currOriginal = currOriginal->next;
}
return newHead;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
Node* copied = copyList(head);
printList(copied);
return 0;
}Output
10 20 30Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static Node copyList(Node head) {
if (head == null)
return null;
Node newHead = new Node(head.data);
Node currOriginal = head.next;
Node currCopy = newHead;
while (currOriginal != null) {
currCopy.next = new Node(currOriginal.data);
currCopy = currCopy.next;
currOriginal = currOriginal.next;
}
return newHead;
}
}
Output
10 20 30Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def copy_list(head):
if not head:
return None
new_head = Node(head.data)
curr_original = head.next
curr_copy = new_head
while curr_original:
curr_copy.next = Node(curr_original.data)
curr_copy = curr_copy.next
curr_original = curr_original.next
return new_head
Output
10 20 30JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function copyList(head) {
if (head === null)
return null;
let newHead = new Node(head.data);
let currOriginal = head.next;
let currCopy = newHead;
while (currOriginal !== null) {
currCopy.next = new Node(currOriginal.data);
currCopy = currCopy.next;
currOriginal = currOriginal.next;
}
return newHead;
}
Output
10 20 30Approach 2 — Recursive Copy
Idea
Use recursion to copy nodes one by one.
Each recursive call creates a node and connects it to the copy of the remaining list.
Steps
- Base case:
- If head is NULL → return NULL
- Create new node with current data
- Recursively copy remaining list
- Attach returned node to new node
Time Complexity
O(N)
Space Complexity
O(N)
(recursion stack + new nodes)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* copyList(struct Node* head) {
if (head == NULL)
return NULL;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = head->data;
newNode->next = copyList(head->next);
return newNode;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
struct Node* copied = copyList(head);
printList(copied);
return 0;
}Output
10 20 30
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
data = x;
next = NULL;
}
};
Node* copyList(Node* head) {
if (head == NULL)
return NULL;
Node* newNode = new Node(head->data);
newNode->next = copyList(head->next);
return newNode;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
Node* copied = copyList(head);
printList(copied);
return 0;
}Output
10 20 30
Java Implementation
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
public class Main {
static Node copyList(Node head) {
if (head == null)
return null;
Node newNode = new Node(head.data);
newNode.next = copyList(head.next);
return newNode;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
Node copied = copyList(head);
printList(copied);
}
}
Output
10 20 30
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def copy_list(head):
if not head:
return None
new_node = Node(head.data)
new_node.next = copy_list(head.next)
return new_node
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
copied = copy_list(head)
print_list(copied)
Output
10 20 30
JavaScript Implementation
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function copyList(head) {
if (head === null)
return null;
let newNode = new Node(head.data);
newNode.next = copyList(head.next);
return newNode;
}
function printList(head) {
while (head !== null) {
process.stdout.write(head.data + " ");
head = head.next;
}
}
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
let copied = copyList(head);
printList(copied);
Output
10 20 30
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.jpg)
.jpg)
