Clone a linked list with next and random pointer

Clone a linked list with next and random pointer

GeeksforGeeks

???? Problem:

You are given a linked list where each node has a next pointer and a random pointer. The task is to clone the list such that both the next and random pointers of the new nodes point to the corresponding nodes in the copied list, with no reference to the original list.


?? Example:

  • Input: LinkedList: 1 → 2 → 3 → 4, Random Pointers = [{1,2}, {2,4}]
  • Output: A new cloned list with the same structure and random pointers.


?? Approach:

To solve this problem efficiently with O(n) time complexity and O(1) space complexity, we'll adopt a three-step approach:

  1. Step 1: Duplicate Nodes Insert a copy of each node right after the original node in the linked list. This will help us manage both next and random pointers later.
  2. Step 2: Fix Random Pointers For each new node, set its random pointer to the corresponding new node using the original list's random pointers.
  3. Step 3: Separate the Lists Finally, split the combined linked list into two separate lists: one is the original, and the other is the newly copied list.


?? Sample Code:

class Node {
    int data;
    Node next, random;

    Node(int d) {
        data = d;
        next = random = null;
    }
}

class Solution {
    // Function to clone a linked list with next and random pointer.
    Node copyList(Node head) {
        if (head == null) return null;

        // Step 1: Insert copy nodes
        Node curr = head;
        while (curr != null) {
            Node newNode = new Node(curr.data);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }

        // Step 2: Fix random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Separate the lists
        curr = head;
        Node copyHead = head.next;
        Node copy = copyHead;
        while (curr != null) {
            curr.next = curr.next.next;
            if (copy.next != null) {
                copy.next = copy.next.next;
            }
            curr = curr.next;
            copy = copy.next;
        }

        return copyHead;
    }
}        

?? Time Complexity:

  • O(n) because we traverse the linked list multiple times but still in a linear fashion.

?? Summary:

Using a three-step approach (duplicating nodes, setting random pointers, and separating the lists), we achieve a cloned linked list in optimal time and space complexity. The beauty of this approach is its space efficiency, with O(1) extra space being used!



要查看或添加评论,请登录

Pathan Ismailkhan的更多文章

  • Array Subset

    Array Subset

    ?? Problem: You're given two arrays: a1[] and a2[], where both may contain duplicates, and the goal is to determine…

  • Intersection Point in Linked Lists

    Intersection Point in Linked Lists

    When working with linked lists, finding where two lists intersect can be tricky especially when efficiency is crucial!…

  • Is Linked List Length Even?

    Is Linked List Length Even?

    To solve the problem of determining if the length of a linked list is even or odd, let's consider an efficient approach…

  • Count Linked List Nodes

    Count Linked List Nodes

    ?? Problem: Today’s challenge is a fundamental one in data structures—finding the length of a Singly Linked List. ??…

  • Two Smallests in Every Subarray

    Two Smallests in Every Subarray

    ? Short Summary: In today's CODE OF THE DAY, we tackle how to find the maximum sum of the two smallest elements in…

  • Reorganize The Array

    Reorganize The Array

    ?? Summary: In today’s "Code of the Day," we explore an exciting problem: rearranging an array so that arr[i] = i. ??…

  • Max distance between same elements

    Max distance between same elements

    ?? Summary: In today’s "Code of the Day," we tackle a classic problem: finding the maximum distance between repeated…

    3 条评论
  • Largest Pair Sum

    Largest Pair Sum

    To solve the problem of finding the largest pair sum in an array of distinct integers, we can utilize a simple and…

  • Not a subset sum

    Not a subset sum

    ????? Problem: Given a sorted array of positive integers, find the smallest positive integer that cannot be represented…

  • 2491. Divide Players Into Teams of Equal Skill

    2491. Divide Players Into Teams of Equal Skill

    ????? Problem: You are given an even-length array of players' skills and the goal is to divide them into teams of 2…

社区洞察

其他会员也浏览了