js

Saturday, August 27, 2022

Clone a Linked List with next and Random Pointer

 


  • Difficulty Level : Hard
  • Last Updated : 28 Jul, 2022

An example of linked list with a random pointerGiven a linked list of size N where each node has two links: one pointer points to the next node and the second pointer points to any node in the list. The task is to create a clone of this linked list in O(N) time. 

Note: The pointer pointing to the next node is ‘next‘ pointer and the one pointing to an arbitrary node is called ‘arbit’ pointer as it can point to any arbitrary node in the linked list. 

An example of the linked list is shown in the below image:

An example of linked list with a random pointerAn example of linked list with a random pointer

An example of linked list with a random pointerAn example of linked list with a random pointer


Approach 1 (Using Extra Space): The idea to solve this problem is: 

First create a single linked list with only the ‘next’ pointer and use a mapping to map the new nodes to their corresponding nodes in the given linked list. Now use this mapping to point the arbitrary node from any node in the newly created list. 

Follow the steps mentioned beloved to implement the above idea:

  • Create a duplicate (say Y) for each node (say X) and map them with corresponding old nodes (say mp, So mp[X] = Y).
  • Create the single linked list of the duplicate nodes where each node only has the ‘next’ pointer.
  • Now iterate over the old linked list and do the following:
    • Find the duplicate node mapped with the current one. (i.e., if the current node is X then duplicate is mp[x])
    • Make the arbit pointer of the duplicate node pointing to the duplicate of the current->arbit node (i.e., mp[x]->arbit will point to mp[X->arbit]).
  • The linked list created in this way is the required linked list. 

Follow the illustration below for a better understanding:

Illustration:

Consider the linked list shown below:

Original linked list

Original linked list 

The green links are the arbit pointers

Creating copy of Nodes and next pointer:

Initially create single linked list of duplicate nodes with only the next pointers and map them with the old ones. 
Here the blue coloured links are used to show the mapping.

New linked list mapped with old nodes

Linking the arbit pointers:

Now iterating the old array and update the arbit pointers as mentioned in the approach. The green coloured links are the arbit pointers.

At first node:

Linking arbit pointer of duplicate of 1st node

Linking arbit pointer of duplicate of 1st node

At sconde node:

Linking arbit pointer of duplicate of 2nd node

Linking arbit pointer of duplicate of 2nd node

At third node:

Linking arbit pointer of duplicate of 3rd node

Linking arbit pointer of duplicate of 3rd node

At fourth node:

Linking arbit pointer of duplicate of 4th node

Linking arbit pointer of duplicate of 4th node

At fifth node:

Linking arbit pointer of duplicate of 5th node

Linking arbit pointer of duplicate of 5th node

The final linked list is as shown below:

The original and the clone

The original and the clone

Below is the implementation of the above approach:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node of linked list
struct Node {
    int val;
    Node* next;
    Node* arbit;
   
    // Constructor
    Node(int x)
    {
        this->val = x;
        this->next = NULL;
        this->arbit = NULL;
    }
};
 
// Function to clone the linked list
Node* cloneLinkedList(Node* head)
{
    // Map to store the mapping of
    // old nodes with new ones
    unordered_map<Node*, Node*> mp;
    Node *temp, *nhead;
   
    // Duplicate of the first node
    temp = head;
    nhead = new Node(temp->val);
    mp[temp] = nhead;
   
    // Loop to create duplicates of nodes
    // with only next pointer
    while (temp->next != NULL) {
        nhead->next
            = new Node(temp->next->val);
        temp = temp->next;
        nhead = nhead->next;
        mp[temp] = nhead;
    }
    temp = head;
   
    // Loop to clone the arbit pointers
    while (temp != NULL) {
        mp[temp]->arbit = mp[temp->arbit];
        temp = temp->next;
    }
   
    // Return the head of the clone
    return mp[head];
}
 
// Function to print the linked list
void printList(Node* head)
{
    cout << head->val << "("
         << head->arbit->val << ")";
    head = head->next;
    while (head != NULL) {
        cout << " -> " << head->val << "("
             << head->arbit->val << ")";
        head = head->next;
    }
    cout << endl;
}
 
// Driver code
int main()
{
    // Creating a linked list with random pointer
    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);
    head->arbit = head->next->next;
    head->next->arbit = head;
    head->next->next->arbit
        = head->next->next->next->next;
    head->next->next->next->arbit
        = head->next->next;
    head->next->next->next->next->arbit
        = head->next;
   
    // Print the original list
    cout << "The original linked list:\n";
    printList(head);
   
    // Function call
    Node* sol = cloneLinkedList(head);
   
    cout << "The cloned linked list:\n";
    printList(sol);
   
    return 0;
}

Time Complexity: O(N) 
Auxiliary Space: O(N) 

Approach 2 (Using Constant Extra Space):  The idea to solve is using constant extra space is:

Create duplicate of a node and insert it in between that node and the node just next to it. 

Now for a node X its duplicate will be X->next and the arbitrary pointer of the duplicate will point to X->arbit->next [as that is the duplicate of X->arbit]

Follow the steps mentioned below to implement the idea:

  • Create the copy of node 1 and insert it between node 1 and node 2 in the original Linked List, create the copy of node 2 and insert it between 2nd and 3rd node and so on. Add the copy of N after the Nth node 
  • Now copy the arbitrary link in this fashion:

original->next->arbitrary = original->arbitrary->next 

  • Now restore the original and copy linked lists in this fashion in a single loop. 

original->next = original->next->next;
copy->next = copy->next->next;

  • Make sure that the last element of original->next is NULL. 

Refer the below post for implementation of this method. 
Clone a linked list with next and random pointer in O(1) space 
Time Complexity: O(N) 
Auxiliary Space: O(1)

Delete Nth node from the end of the given linked list

 


  • Difficulty Level : Medium
  • Last Updated : 12 Jul, 2022

Given a linked list and an integer N, the task is to delete the Nth node from the end of the given linked list.
 

Examples:  

Input: 2 -> 3 -> 1 -> 7 -> NULL, N = 1 
Output: 
The created linked list is: 
2 3 1 7 
The linked list after deletion is: 
2 3 1

Input: 1 -> 2 -> 3 -> 4 -> NULL, N = 4 
Output: 
The created linked list is: 
1 2 3 4 
The linked list after deletion is: 
2 3 4 

Intuition:

Lets  K be the total nodes in the linked list.

Observation : The Nth node from the end is (K-N+1)th node from the beginning.

So the problem simplifies down to that we have to find  (K-N+1)th node from the beginning.

  • One way of doing it is to find the length (K) of the linked list in one pass and then in the second pass move (K-N+1) step from the beginning to reach the Nth node from the end.
  • To do it in one pass. Let’s take the first pointer and move N step from the beginning. Now the first pointer is (K-N+1) steps away from the last node, which is the same number of steps the second pointer require to move from the beginning to reach the Nth node from the end.

Approach:  

  • Take two pointers; the first will point to the head of the linked list and the second will point to the Nth node from the beginning.
  • Now keep incrementing both the pointers by one at the same time until the second is pointing to the last node of the linked list.
  • After the operations from the previous step, the first pointer should point to the Nth node from the end now. So, delete the node the first pointer is pointing to.

Below is the implementation of the above approach: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
class LinkedList {
public:
    // Linked list Node
    class Node {
    public:
        int data;
        Node* next;
        Node(int d)
        {
            data = d;
            next = NULL;
        }
    };
 
    // Head of list
    Node* head;
 
    // Function to delete the nth node from the end of the
    // given linked list
    Node* deleteNode(int key)
    {
        // We will be using this pointer for holding address
        // temporarily while we delete the node
        Node* temp;
 
        // First pointer will point to the head of the
        // linked list
        Node* first = head;
 
        // Second pointer will point to the Nth node from
        // the beginning
        Node* second = head;
        for (int i = 0; i < key; i++) {
            // If count of nodes in the given linked list is <= N
            if (second->next == NULL) {
                // If count = N i.e. delete the head node
                if (i == key - 1) {
                    temp = head;
                    head = head->next;
                    free(temp);
                }
                return head;
            }
            second = second->next;
        }
 
        // Increment both the pointers by one until second
        // pointer reaches the end
        while (second->next != NULL) {
            first = first->next;
            second = second->next;
        }
        // First must be pointing to the Nth node from the
        // end by now So, delete the node first is pointing to
        temp = first->next;
        first->next = first->next->next;
        free(temp);
        return head;
    }
 
    // Function to insert a new Node at front of the list
    Node* push(int new_data)
    {
        Node* new_node = new Node(new_data);
        new_node->next = head;
        head = new_node;
        return head;
    }
 
    // Function to print the linked list
    void printList()
    {
        Node* tnode = head;
        while (tnode != NULL) {
            cout << (tnode->data) << (" ");
            tnode = tnode->next;
        }
    }
};
 
// Driver code
int main()
{
    LinkedList* llist = new LinkedList();
 
    llist->head = llist->push(7);
    llist->head = llist->push(1);
    llist->head = llist->push(3);
    llist->head = llist->push(2);
 
    cout << ("Created Linked list is:\n");
    llist->printList();
 
    int N = 1;
    llist->head = llist->deleteNode(N);
 
    cout << ("\nLinked List after Deletion is:\n");
    llist->printList();
}
 
// This code is contributed by Sania Kumari Gupta
Output
Created Linked list is:
2 3 1 7 
Linked List after Deletion is:
2 3 1 

we already covered the iterative version above,
Now let us see its recursive approach as well,
 

Recursive Approach :
1) Create a dummy node and create a link from dummy node to head node. i.e, dummy->next = head 
2) Then we will use the recursion stack to keep track of elements that are being pushed in recursion calls.
3) While popping the elements from recursion stack, we will decrement the N(position of target node from the end of linked list) i.e, N = N-1.
4) When we reach (N==0) that means we have reached at the target node,
5) But here is the catch, to delete the target node we require its previous node,
6) So we will now stop when (N==-1) i.e, we reached the previous node.
7) Now it is very simple to delete the node by using previousNode->next = previousNode->next->next.
 

// C++ implementation of the approach
// Code is contributed by Paras Saini
#include <bits/stdc++.h>
using namespace std;
class LinkedList {
public:
    int val;
    LinkedList* next;
 
    LinkedList()
    {
        this->next = NULL;
        this->val = 0;
    }
    LinkedList(int val)
    {
        this->next = NULL;
        this->val = val;
    }
 
    LinkedList* addNode(int val)
    {
        if (this == NULL) {
            return new LinkedList(val);
        }
        else {
            LinkedList* ptr = this;
            while (ptr->next) {
                ptr = ptr->next;
            }
            ptr->next = new LinkedList(val);
            return this;
        }
    }
 
    void removeNthNodeFromEndHelper(LinkedList* head,
                                    int& n)
    {
        if (!head)
            return;
        // Adding the elements in the recursion
        // stack
        removeNthNodeFromEndHelper(head->next, n);
        // Popping the elements from recursion stack
        n -= 1;
        // If we reach the previous of target node
        if (n == -1){
            LinkedList* temp = head->next;
            head->next = head->next->next;
            free (temp);
        }
    }
 
    LinkedList* removeNthNodeFromEnd(int n)
    {
        // return NULL if we have NULL head or only
        // one node.
        if (!this or !this->next)
            return NULL;
 
        // Create a dummy node and point its next to
        // head.
        LinkedList* dummy = new LinkedList();
        dummy->next = this;
 
        // Call function to remove Nth node from end
        removeNthNodeFromEndHelper(dummy, n);
 
        // Return new head i.e, dummy->next
        return dummy->next;
    }
 
    void printLinkedList()
    {
        if (!this) {
            cout << "Empty List\n";
            return;
        }
        LinkedList* ptr = this;
        while (ptr) {
            cout << ptr->val << " ";
            ptr = ptr->next;
        }
        cout << endl;
    }
};
 
class TestCase {
private:
    void printOutput(LinkedList* head)
    {
        // Output:
        if (!head)
            cout << "Empty Linked List\n";
        else
            head->printLinkedList();
    }
    void testCase1()
    {
        LinkedList* head = new LinkedList(1);
        head = head->addNode(2);
        head = head->addNode(3);
        head = head->addNode(4);
        head = head->addNode(5);
        head->printLinkedList(); // Print: 1 2 3 4 5
        head = head->removeNthNodeFromEnd(2);
        printOutput(head); // Output: 1 2 3 5
    }
 
    void testCase2()
    {
        // Important Edge Case, where linkedList [1]
        // and n=1,
        LinkedList* head = new LinkedList(1);
        head->printLinkedList(); // Print: 1
        head = head->removeNthNodeFromEnd(2);
        printOutput(head); // Output: Empty Linked List
    }
 
    void testCase3()
    {
        LinkedList* head = new LinkedList(1);
        head = head->addNode(2);
        head->printLinkedList(); // Print: 1 2
        head = head->removeNthNodeFromEnd(1);
        printOutput(head); // Output: 1
    }
 
public:
    void executeTestCases()
    {
        testCase1();
        testCase2();
        testCase3();
    }
};
 
int main()
{
    TestCase testCase;
    testCase.executeTestCases();
    return 0;
}
Output
1 2 3 4 5 
1 2 3 5 
1 
Empty Linked List
1 2 
1 

Two Pointer Approach – Slow and Fast Pointers

This problem can be solved by using two pointer approach as below:

  • Take two pointers – fast and slow. And initialize their values as head node
  • Iterate fast pointer till the value of n.
  • Now, start iteration of fast pointer till the None value of the linked list. Also, iterate slow pointer.
  • Hence, once the fast pointer will reach to the end the slow pointer will reach the node which you want to delete.
  • Replace the next node of the slow pointer with the next to next node of the slow pointer.

// C++ code for the deleting a node from end using two
// pointer approach
 
#include <iostream>
using namespace std;
 
class LinkedList {
public:
    // structure of a node
    class Node {
    public:
        int data;
        Node* next;
        Node(int d)
        {
            data = d;
            next = NULL;
        }
    };
 
    // Head node
    Node* head;
 
    // Function for inserting a node at the beginning
    void push(int data)
    {
        Node* new_node = new Node(data);
        new_node->next = head;
        head = new_node;
    }
 
    // Function to display the nodes in the list.
    void display()
    {
        Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << endl;
            temp = temp->next;
        }
    }
 
    // Function to delete the nth node from the end.
    void deleteNthNodeFromEnd(Node* head, int n)
    {
        Node* fast = head;
        Node* slow = head;
 
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
 
        if (fast == NULL) {
            return;
        }
 
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return;
    }
};
 
int main()
{
 
    LinkedList* l = new LinkedList();
 
    // Create a list 1->2->3->4->5->NULL
    l->push(5);
    l->push(4);
    l->push(3);
    l->push(2);
    l->push(1);
    cout << "***** Linked List Before deletion *****"
         << endl;
    l->display();
 
    cout << "************** Delete nth Node from the End "
            "*****"
         << endl;
    l->deleteNthNodeFromEnd(l->head, 2);
 
    cout << "*********** Linked List after Deletion *****"
         << endl;
    l->display();
 
    return 0;
}
 
// This code is contributed by lokesh (lokeshmvs21).
Output
***** Linked List Before deletion *****
1
2
3
4
5
************** Delete nth Node from the End *****
*********** Linked List after Deletion *****
1
2
3
5

Time complexity: O(n)

Space complexity: O(1) using constant space

Rearrange a linked list in to alternate first and last element

 


  • Difficulty Level : Hard
  • Last Updated : 15 Aug, 2022

Given a linked list. arrange the linked list in manner of alternate first and last element.

Examples: 

Input : 1->2->3->4->5->6->7->8
Output :1->8->2->7->3->6->4->5

Input :10->11->15->13
Output :10->13->11->15

We have discussed three different solution in Rearrange a given linked list in-place.
In this post a different Deque based solution is discussed.

Method:

  1. Create an empty deque 
  2. Insert all element from the linked list to the deque 
  3. Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on 
 

 Implementation:

// CPP program to rearrange a linked list in given manner
#include <bits/stdc++.h>
using namespace std;
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* Function to reverse the linked list */
void arrange(struct Node* head)
{
    struct Node* temp = head;
    deque<int> d; // defining a deque
 
    // push all the elements of linked list in to deque
    while (temp != NULL) {
        d.push_back(temp->data);
        temp = temp->next;
    }
 
    // Alternatively push the first and last elements
    // from deque to back to the linked list and pop
    int i = 0;
    temp = head;
    while (!d.empty()) {
        if (i % 2 == 0) {
            temp->data = d.front();
            d.pop_front();
        }
        else {
            temp->data = d.back();
            d.pop_back();
        }
        i++;
        temp = temp->next; // increase temp
    }
}
 
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
changes the head */
void push(struct Node** head_ref, char new_data)
{
    /* allocate node */
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
// printing the linked list
void printList(struct Node* head)
{
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
}
 
/* Driver program to test above function*/
int main()
{
    // Let us create linked list 1->2->3->4
    struct Node* head = NULL;
 
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "Given linked list\t";
    printList(head);
    arrange(head);
    cout << "\nAfter rearrangement\t";
    printList(head);
    return 0;
}
Output
Given linked list    1  2  3  4  5  
After rearrangement    1  5  2  4  3  

Time Complexity : O(nlogn)

Auxiliary space: O(n) because using deque

  Write a Program to Find the Maximum Depth or Height of a Tree Difficulty Level : Easy Last Updated : 21 Jul, 2022 Read Discuss Given ...