Being Code Expert: Linklist

Showing posts with label Linklist. Show all posts

Linked list programming questions

Linked list programming questions

Remove kth node from last of linked list

Given a singly linked list and an integer k, remove the k^th last element from the list. k is guaranteed to be smaller than the length of the list.

The list is very long, so making more than one pass is prohibitively expensive.

Example:

Input:  5->2->8->4->1->NULL,  k = 3
Output: 5 2 4 1

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

//function to traverse(print) a linked
//list
void linkedListTraversal(Node *head)
{
    Node *temp = head;
    //iterate till we reach end of the linked
    //list
    while (temp != NULL)
    {
        //print the current
        //node data
        cout << temp->data << " ";
        //move to next node
        temp = temp->next;
    }
}

//function to find the length of
//inked list
int linkedListLength(Node *node)
{
    int length = 0;

    while (node != NULL)
    {
        node = node->next;
        length++;
    }
    return length;
}

//function to remove nth node
//from end of list
Node *removetNthNodeFromEnd(Node *head, int n, int length)
{
    // If list is empty or n=0
    if (head == NULL || n == 0)
    {
        return head;
    }
    // if delete first element
    // Base case
    if (n == length)
    {
        return head->next;
    }

    int count = 0;
    Node *root = head;
    Node *prev = head;

    while (root != NULL)
    {
        count++;
        // if found nth then delete
        if (count == length - n + 1)
        {
            prev->next = root->next;
            free(root);
            break;
        }
        // change previous
        prev = root;
        // head->next
        root = root->next;
    }
    return head;
}
int main()
{
    Node *head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(8);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(1);
    int length = linkedListLength(head);
    int k = 3;
    head = removetNthNodeFromEnd(head, k, length);
    linkedListTraversal(head);
    return 0;
}

Deep Clone the linked list

Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list.

Example:

Input:  head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int val;
    Node *next;
    Node *random;

    Node(int val)
    {
        this->val = val;
        this->next = NULL;
        this->random = NULL;
    }
};

Node *copyRandomList(Node *head)
{
    Node *curr = head, *temp = NULL;
    if (head == NULL)
        return NULL;
    // insert duplicate node of every node into  the list
    while (curr)
    {
        temp = curr->next;

        //create new node with the same value as of the
        //current node
        curr->next = new Node(curr->val);

        //settle the pointers
        curr->next->next = temp;

        //move to the next node
        curr = temp;
    }
    curr = head;
    while (curr)
    {

        //if current next is present then
        //mark the current random pointer
        if (curr->next)
            curr->next->random = curr->random ? 
       curr->random->next : curr->random;

        //move to the next node
        curr = curr->next ? curr->next->next : curr->next;
    }
    Node *original = head, *copy = head->next;
    temp = copy;

    //settle the pointers in original and copy of
    //the list
    while (original && copy)
    {

        //if original next present then
        //move original to next of next of original
        original->next = original->next ? 
        original->next->next : original->next;
        copy->next = copy->next ?
       copy->next->next : copy->next;

        //move to the next node in original of linked
        //list
        original = original->next;

        //move to the next node in the copy of linked
        //ist
        copy = copy->next;
    }
    return temp;
}

//function to print the linked list
void printList(Node *head)
{
    Node *temp = head;
    cout << "[";
    while (temp != NULL)
    {
        cout << "[";
        cout << temp->val << ",";
        if (temp->random != NULL)
            cout << temp->random->val;
        else
            cout << "null";
        cout << "]";

        temp = temp->next;
        if (temp != NULL)
            cout << ",";
    }
    cout << "]";
}
int main()
{

    Node *head = new Node(1);
    head->next = new Node(2);
    Node *temp = head->next;
    head->random = head;
    temp->random = head;
    head->random = head;
    head = copyRandomList(head);
    printList(head);
    return 0;
}

Swap every two nodes

Given the head of a singly linked list, swap every two nodes and return its head.

For example, given 1 -> 2 -> 3 -> 4, return 2 -> 1 -> 4 -> 3.

Example:

Input:  1->2->3->4->NULL
Output: 2 1 4 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
//Function to swap nodes in pair in
//linklist
Node *swapPairs(Node *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *temp = head;
    while (temp != NULL)
    {
        if (temp->next != NULL)
        {
            int val = temp->data;
            temp->data = temp->next->data;
            temp->next->data = val;
            temp = temp->next;
        }
        temp = temp->next;
    }
    return head;
}
int main()
{
    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head = swapPairs(head);
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}
//Time Complexity: O(n)
//Space Complexity:O(1)

Merge In Between Linked Lists

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

Example:

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [0,1,2,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct ListNode
{
    int data;
    ListNode *next;
    ListNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

ListNode *mergeInBetween(ListNode *list1, int a, int b, 
   ListNode *list2)
{
    ListNode *prev = NULL;
    ListNode *temp = list1;
    int i = 0;
    while (i < a)
    {
        prev = temp;
        temp = temp->next;
        i++;
    }
    prev->next = list2;
    while (prev->next != NULL)
    {
        prev = prev->next;
    }
    while (i < b)
    {
        temp = temp->next;
        i++;
    }
    prev->next = temp->next;
    return list1;
}
//function to traverse a linked
//list
void linkedListTraversal(ListNode *head)
{
    ListNode *temp = head;
    //iterate till we reach end of the linked
    //list
    while (temp != NULL)
    {
        //print the current
        //node data
        cout << temp->data;
        //move to next node

        temp = temp->next;
        if (temp != NULL)
            cout << ", ";
    }
}
int main()
{
    ListNode *list1 = new ListNode(0);
    list1->next = new ListNode(1);
    list1->next->next = new ListNode(2);
    list1->next->next->next = new ListNode(3);
    list1->next->next->next->next = new ListNode(4);
    list1->next->next->next->next->next = new ListNode(5);

    int a = 3, b = 4;

    ListNode *list2 = new ListNode(1000000);
    list2->next = new ListNode(1000001);
    list2->next->next = new ListNode(1000002);

    ListNode *merge = mergeInBetween(list1, a, b, list2);
    cout << "[";
    linkedListTraversal(merge);
    cout << "]";
    return 0;
}

Swapping Nodes in a Linked List

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//Struture of  node
struct ListNode
{
    int data;
    ListNode *next;
    ListNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
ListNode *swapNodes(ListNode *head, int k)
{
    int n = 0;
    ListNode *temp = head, *temp1 = head, *temp3 = NULL;

    while (temp != NULL)
    {
        n++;
        if (n == k)
        {
            temp3 = temp;
        }
        temp = temp->next;
    }

    int y = n - k + 1;

    while (temp1 != NULL)
    {
        y--;
        if (y == 0)
        {
            break;
        }
        temp1 = temp1->next;
    }

    swap(temp1->data, temp3->data);
    return head;
}
//function to traverse a linked
//list
void linkedListTraversal(ListNode *head)
{
    ListNode *temp = head;
    //iterate till we reach end of the linked
    //list
    while (temp != NULL)
    {
        //print the current
        //node data
        cout << temp->data << " ";
        //move to next node
        temp = temp->next;
    }
}
int main()
{
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    int k = 2;

    head = swapNodes(head, k);

    linkedListTraversal(head);

    return 0;
}

Merge k sorted singly linked list

Given k sorted singly-linked lists, write a function to merge all the lists into one sorted singly linked list.

Example:

Input:  list1: 1->3->4->NULL, list2: 3->5->6->NULL, list3: 2->4->5->7->NULL
Output: New list
1 2 3 3 4 4 5 5 6 7

Approach

Java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class MergeKSortedList {
    public static void main(String[] args) {
        // Linked list list to hold all linked list
        List<ListNode> lists = new ArrayList<ListNode>();

        // create first list
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        lists.add(l1);
        // second list
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(4);
        l2.next.next.next.next = new ListNode(5);
        lists.add(l2);
        // third list
        ListNode l3 = new ListNode(1);
        l3.next = new ListNode(5);
        l3.next.next = new ListNode(8);
        lists.add(l3);
        // call for mergeKLists

        ListNode merge = mergeKLists(lists);
        System.out.println("Merge List is");
        linkedListTraversal(merge);
    }

    // method for merge K list
    private static ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        ListNode merge = lists.get(0);
        // iterate till end of list
        for (int i = 1; i < lists.size(); i++) {
            // merge two lists
            ListNode next = lists.get(i);
            merge = merge(merge, next);
        }
        return merge;
    }

    // method for merge two list
    private static ListNode merge(ListNode merge, ListNode next) {
        // base condition
        if (merge == null)
            return next;
        if (next == null)
            return merge;
        ListNode tmp1 = merge;
        ListNode tmp2 = next;
        ListNode root = null;
        ListNode tmp = null;
        int flag = 0;
        while (tmp1 != null && tmp2 != null) {
            // first less then
            if (tmp1.val < tmp2.val) {
                if (flag == 0) {
                    flag = 1;
                    root = tmp1;
                    tmp = root;
                } else {
                    tmp.next = tmp1;
                    tmp = tmp.next;
                }
                tmp1 = tmp1.next;
            } else {
                if (flag == 0) {
                    flag = 1;
                    root = tmp2;
                    tmp = root;
                } else {
                    tmp.next = tmp2;
                    tmp = tmp.next;

                }
                if (tmp2 != null)
                    tmp2 = tmp2.next;
            }
        }
        if (tmp1 != null)
            tmp.next = tmp1;
        if (tmp2 != null)
            tmp.next = tmp2;
        return root;

    }

    // method for traversal list
    private static void linkedListTraversal(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
}


class ListNode implements Comparable<ListNode> {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public int compareTo(ListNode o) {
        if (this.val == o.val)
            return 0;
        else if (this.val > o.val)
            return 1;
        else
            return -1;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//Struture of  node
struct Node
{
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

//function to traverse a linked
//list
void linkedListTraversal(Node *head)
{
    Node *temp = head;
    //iterate till we reach end of the linked
    //list
    while (temp != NULL)
    {
        //print the current
        //node data
        cout << temp->data << " ";
        //move to next node
        temp = temp->next;
    }
}

//function to merge two sorted lists
Node *merge(Node *l1, Node *l2)
{
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    Node *temp1 = l1, *temp2 = l2, *root = NULL, *temp;
    int flag = 0;
    while (temp1 != NULL && temp2 != NULL)
    {
        if (temp1->data < temp2->data)
        {
            if (flag == 0)
            {
                flag = 1;
                root = temp1;
                temp = root;
            }
            else
            {
                temp->next = temp1;

                temp = temp->next;
            }
            temp1 = temp1->next;
        }
        else
        {
            if (flag == 0)
            {
                flag = 1;
                root = temp2;
                temp = root;
            }
            else
            {
                temp->next = temp2;

                temp = temp->next;
            }
            temp2 = temp2->next;
        }
    }
    if (temp1 != NULL)
        temp->next = temp1;
    if (temp2 != NULL)
        temp->next = temp2;
    return root;
}

//function to merge k sorted list
Node *mergeKLists(vector<Node *> &lists)
{
    if (lists.size() == 0)
        return NULL;
    Node *l = lists[0];
    for (int i = 1; i < lists.size(); i++)
    {
        //merge two lists
        Node *temp1 = lists[i];
        l = merge(l, temp1);
    }
    return l;
}
int main()
{

    //list 1: 1->3->4
    Node *l1 = new Node(1);
    l1->next = new Node(3);
    l1->next->next = new Node(4);

    //list 2: 3->5->6
    Node *l2 = new Node(3);
    l2->next = new Node(5);
    l2->next->next = new Node(6);

    //list 3: 2->4->5->7
    Node *l3 = new Node(2);
    l3->next = new Node(4);
    l3->next->next = new Node(5);
    l3->next->next->next = new Node(7);

    //vector to hold the all lists
    vector<Node *> lists;
    lists.push_back(l1);
    lists.push_back(l2);
    lists.push_back(l3);

    //call for mergeKLists
    Node *node = mergeKLists(lists);
    cout << "New list\n";
    linkedListTraversal(node);
    return 0;
}

Home

Linked list programming questions

Remove kth node from last of linked list

Deep Clone the linked list

Swap every two nodes

Merge In Between Linked Lists

Swapping Nodes in a Linked List

Merge k sorted singly linked list