How do you copy a linked list into another list?
Solution 1
The logic for duplicating a linked list is recursive and based on the following observations:
- The clone of the empty list is the empty list.
- The clone of a list with first node x and remaining nodes xs is a copy of x prepended to a clone of xs.
If you encode the linked list in C++, this can be very clean:
struct Node {
int value;
Node* next;
};
Node* Clone(Node* list) {
if (list == NULL) return NULL;
Node* result = new Node;
result->value = list->value;
result->next = Clone(list->next);
return result;
}
Solution 2
Do you understand how to add a new node to an existing list? And do you understand how to traverse (i.e. iterate over) a list? Copying a list is just performing both of these operations simultaneously (traverse ListA; for each element, copy the element and add it as a new node to ListB).
Solution 3
The answer to this post has been given and accepted - all good! However, if someone is looking for an iterative approach in C#, here it is:
The Node class:
public class Node
{
public Node(int val)
{
Val = val;
}
public Node Next { get; set; }
public int Val { get; }
}
Here is the iterative implementation:
public Node CopyLinkedListIteratively(Node head)
{
// validation:
if (head == null) return null;
// current node is always a 'new' node with value.
Node currentNode = new Node(head.Val);
// set copyList and previous to current node to start with - which is true at this point in time!
Node copyList = currentNode;
Node previous = currentNode;
// move head one step forward as we already have copied its value.
head = head.Next;
// keep moving until we hit a null reference which is the end.
while (head != null)
{
currentNode = new Node(head.Val); // create a new node every time as we move forward.
previous.Next = currentNode; // set previous node's next to current node as previous node itself is one step behind the current.
previous = previous.Next; // move prev pointer forward
head = head.Next; // move head pointer forward as well
}
// return the reference to copyList.
// copyList and previous both started off pointing to the currentNode, then in the while loop
// previous kept moving forward till all nodes are copied.
// copyList reference never moved from its position so its still pointing at the start.
return copyList;
}
Time complexity: O(n)
Space complexity: O(n)
where n = number of nodes in the linked list.
Its personal preference to use recursive or iterative approach, however I would suggest to think about the function call stack when using recursive.
Unit test:
[Test]
public void CopyLinkedListIterativelyTest()
{
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);
head.Next.Next.Next = new Node(4);
head.Next.Next.Next.Next = new Node(5);
var actual = runner.CopyLinkedListIteratively(head);
while (actual != null)
{
Assert.AreEqual(head.Val, actual.Val);
actual = actual.Next;
head = head.Next;
}
}
Related videos on Youtube
Vishwanath Dalvi
SOreadytohelp about me box is kept "", intentionally.
Updated on August 30, 2021Comments
-
Vishwanath Dalvi over 2 years
I'm studying data structures and linked lists, but I'm not getting the concept of how to make a copy of a linked list. Can someone explain this, possibly using pseudocode or C code?