Practice Problems of Linked List

10 mins read725 Views Comment

Updated on Jan 23, 2023 16:20 IST

LinkedList is a linear data structure and part of the collection framework similar to the ArrayList used to store and manipulate the data points. In this article, we will discuss top 10 problems to master linked list.

Before starting with the practice problems on Linked List, you should have a proper understanding of its internal implementation.

As we know that, Linked List is a data structure that consists of nodes which are interconnected via links where each node contains data and the pointer which contains the address of the next node in the memory.

We will discuss few problems on Linked List with varying difficulty levels starting from Easy to Hard. Since Linked List is one of the most asked topics in interviews, these problems will be more than enough for students preparing for placements/ professionals appearing for interviews.

Must Read: Introduction to LinkedList Data Structure

Must Read: Linked List Examples

1. Design and implement Linked List

Input format:

i 1 5 —–> Insert 5 at 1^st position

i 2 6 ——> Insert 6 at 2^nd position

p ———-> Print linked list

d 1 ——-> Delete node at 1^st position

p ———-> Print linked list

Java code:

static Node head;
static int length;

// creating a class Node containing data and pointer to next Node.

public static class Node 
{
    int data;
    Node next;
    Node(int data)
    {
        this.data=data;
    }
}

// inserting node with value given at the given position

public static void insert(int position, int value)
{
    if(position>length+1)
    return;
    Node newNode=new Node(value);  // Create a node of value given in input
    if(position==1)
    {                                                                                                  
                   newNode.next=head;   
       newNode=head; 
    }
    else
    {
        int count=1;
        Node temp=head;
        while(count
<position-1) {="" temp="temp.next;" count++;="" }="" newnode.next="temp.next;" temp.next="newnode;" length++;="" deleting="" node="" at="" a="" given="" position="" public="" static="" void="" delete(int="" position)="" if(position="">
 length)
    return;
    if(position==1)
    head=head.next;
    else
    {
        int count=1;
        Node temp=head;
        while(count
 <position-1) {="" count++;="" temp="temp.next;" }="" temp.next="curr.next.next;" length--;="" printing="" the="" linked="" list="" public="" static="" void="" print()="" output="" each="" element="" followed="" by="" a="" space="" if(length="=" 0)="" return;="" node="" while="" (node.next="" !="null)" system.out.print(node.data+"="" ");="" system.out.print(node.data);="" <="" code="">
</position-1) {="" count++;="" temp="temp.next;" }="" temp.next="curr.next.next;" length--;="" printing="" the="" linked="" list="" public="" static="" void="" print()="" output="" each="" element="" followed="" by="" a="" space="" if(length="=" 0)="" return;="" node="" while="" (node.next="" !="null)" system.out.print(node.data+"="" ");="" system.out.print(node.data);="" <="" code=""></position-1) {="" temp="temp.next;" count++;="" }="" newnode.next="temp.next;" temp.next="newnode;" length++;="" deleting="" node="" at="" a="" given="" position="" public="" static="" void="" delete(int="" position)="" if(position="">
Copy code

Must Read: Circular Linked List

2. Convert Binary Number in a Linked List to Integer

Problem Statement:

The linked list stores binary representation of a number. The value of node in each linked list is either 0 or 1.

Return decimal representation of the number in linked list (MSB is at head of linked list).

E.g.-

Input format: head= [1, 0, 1]

Output: 5

Explanation: (101)_2 = (5)_10

Input format: head=[0]

Output: 0

Approach:

Iterate through the non-empty linked list and retrieve digits from linked list.
Convert binary sequence to decimal number.

(101)_2 = (1*2^2) + (0*2^1) + (1*2^0) = (5)_10

Java function code:

class Solution {
    public int getDecimal(Node head) {
        Node curr=head;
        int ans=0;
        while(curr!=null)
        {
            ans=(ans*2) + curr.val;
            curr=curr.next;
        }
        return ans;
    }
}
Copy code

Time complexity: Time taken to traverse the linked list —> O(n) where n is the size of linked list

Space complexity: No extra space –> O(1)

Must Read: Doubly Linked List

3. Delete node in linked list

Problem Statement:

Write a function to delete a node in linked list. Given reference/ pointer to the node to be deleted and not to the head of the list.

Input format: head = [4,5,6] , node=5

Output format: [4,6]

Explanation: After deleting the reference to the given node, the linked list will become 4—> 6.

Input format: head=[4,5,1,9], node=1

Output format: [4,5,9]

Approach:

Copy the data of next node to the given node.
Delete the next node.

Java function code:

class Solution {
    public void deleteNode(ListNode node) {
        node.val=node.next.val;   
        node.next=node.next.next; // delete the next node
    }
}
Copy code

Time complexity: Copying data of next node + Deleting next node –> O(1) + O(1) = O(1)

Space complexity: No extra space —> O(1)

Programming Online Courses and Certification	Python Online Courses and Certifications
Data Science Online Courses and Certifications	Machine Learning Online Courses and Certifications

Must Read: Singly Linked List

4. Delete N Nodes After M Nodes of a Linked List

Problem statement:

Given head of linked list and two integers, m and n.

Traverse the linked list, keep first m nodes and delete next n nodes. Repeat the process until you reach the end of linked list and return the head of modified list.

Input format: head=[1,2,3,4,5,6,7,8], m=2, n=3

Output format: [1, 2, 6, 7]

Explanation: Keep m=2 nodes (1, 2), then skip n=3 nodes (3, 4, 5). Again, keep m=2 nodes (6, 7) and skip node with values 8 as it reached end of linked list. Head of linked list after removing nodes is returned.

Input format : head= [1,2,3,4,5,6,7,8,9,10,11], m=1, n=3

Output format: [1, 5, 9]

Approach:

Iterate over first m nodes and curr will point to the current node and curr1 to the predecessor of curr node. After m iterations, curr1 will point to mth node.

Iterate over next n nodes. After n iterations when curr reaches the nth node, to delete the nodes between them just change the next pointer of curr1 to curr.

Java function code:

class Solution {
    public Node deleteNode(Node head, int m, int n) {
        Node curr=head;
        Node curr1=head;
        while(curr!=null)
        {
        int count=m;
        while(count!=0 && curr!=null)
        {
            curr1=curr;
            curr=curr.next;
            count--;
        }
        int count1=n;
        while(curr!=null && count1!=0)
        {
            curr=curr.next;
            count1--;
        }
        curr1.next=curr;
        }
        return head;
    }
}
Copy code

Time complexity: Time taken to traverse linked list once —> O(N) where N is the size of linked list

Space complexity: Constant space for variables and two pointers (curr and curr1) —-> O(1)

Also Read: ArrayList vs. LinkedList

5. Middle element of linked list

Problem Statement:

Given head of linked list, return the middle node of linked list (in case of odd-length linked list) and return the second middle node if there are two middle nodes (in case of even-length linked list).

E.g. Odd-length linked list

Even-length linked list

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

Output format: [3, 4, 5]

Explanation: The middle node of the linked list is node 3.

Input format: head=[1,2,3,4,5,6]

Output format: [4, 5, 6]

Explanation: Since the list has two middle values 3 and 4, we will return the second middle node.

Approach 1:

Traverse the entire linked list and find the number of nodes.
Traverse again from the head of linked list till ((no. of nodes/2)+1).

Java function code:

public Node findMid(Node head) {
    Node curr = head;
    
    int total = 0;
    while(curr != null){
        total++;
        curr = curr.next;
    }        
    
    //find the middle one
    total = total/2 + 1;
    
    Node curr1 = head;
    for(int i = 1; i < total; ++i){
        curr1 = curr1.next;
    }
    
    return curr1;
}
Copy code

Time complexity: Traversing entire linked list to find total nodes + Traversing half of linked list to return middle node —> O(N)+ O(N) = O(N)

Space complexity: No extra space —-> O(1)

In 1^st approach, we need to traverse linked list twice.

So, we will see how we can find the middle node of linked list in one-pass.

Approach 2: Fast and Slow Pointer

Starting from head of linked list, while traversing linked list with slow pointer, make another pointer traverse the list twice as fast.

When fast reaches end of linked list, slow would be at middle node.

Java function code:

class Solution {
    public Node middleNode(Node head) {
        Node slow=head;
        Node fast=head;
        while(fast!=null && fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}
Copy code

Time complexity: Traversing entire linked list once —> O(N) where N is the size of linked list

Space complexity: No extra space —-> O(1)

Also Read: Adjacency List

6. Reverse linked list

Problem Statement:

Given head of linked list, reverse the list and return the reversed list.

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

Output format: [5, 4, 3, 2, 1]

Input format: head= [1,2]

Output format: [2, 1]

Input format: head=[]

Output format: []

Approach:

While traversing the linked list, point current element’s next pointer to its previous element and for that, we should track previous node.

Java function code:

class Solution {
    public Node reverse(Node head) {
        Node current=head;
        Node prev=null;
        while(current!=null)
        {    
            Node temp=current.next;
            current.next=prev;
            prev=current;
            current=temp;
            
        }
        return prev;
    }
}
Copy code

Time complexity: Traversing entire linked list once —> O(N) where N is the size of linked list

Space complexity: No extra space as we are reversing the linked list in-place—-> O(1)

Must Read: Data Structure and Algorithm in Python

7. Merge two sorted lists

Problem Statement:

Given heads of two sorted linked lists-list1 and list2, merge them into one sorted linked list and return head of the merged list.

Input format: list1= [1, 2, 4], list2= [1, 3, 4]

Output format: [1, 1, 2, 3, 4, 4]

Input format: list1= [], list2= [0]

Output format: [0]

Input format: list1= [], list2= []

Output format: []

Approach:

Create one temporary node and simultaneously traverse elements of both linked lists one by one and make the temporary node’s next pointer point to the node with smaller element.

Java function code:

class Solution {
    public Node merge(Node list1, Node list2) {
        Node head = new Node(-1);
        if(list1==null && list2==null)
            return list1;
        if(list1==null && list2!=null)
            return list2;
        if(list1!=null && list2==null)
            return list1;
        Node current=head;
        while(list1!=null && list2!=null)
        {
            if(list1.val<=list2.val)
            {
                current.next=list1;
                list1=list1.next;
            }
            else
            {
                current.next=list2;
                list2=list2.next;
            }
            current=current.next;
        }
        current.next=(list1==null)?list2:list1;
        return head.next;
        
    }
}
Copy code

Time complexity: Traversing both linked lists once —> O(M+N) where M is the size of list1 and N is the size of list2.

Space complexity: Only one extra node —-> O(1)

What is Programming	What is Python
What is Data Science	What is Machine Learning

8. Intersection of two Linked List cycle

Problem Statement:

Given heads of two linked lists- head1, head2, return the node at which both the lists intersect otherwise return null.

Input format: head1=[4,1,8,4,5], head2=[5,6,1,8,4,5], intersectingNode=8

Output format: 8

Explanation: The intersected node’s value is 8.

Input format: head1=[2,6,4], head2=[1,5], intersectingNode=0

Output format: null

Explanation: The two lists do not intersect, so return null.

Approach: Two pointers

Calculate the size of both linked lists.

Find the difference between their lengths and start traversing the longer linked list from the start to difference i.e. (b-a).
Start traversing nodes of both linked lists simultaneously and return the node where both intersect otherwise return null.

Java function code:

public class Solution {
    public Node getIntersection(Node head1, Node head2) {
        int n1=size(head1);
        int n2=size(head2);
        int diff=Math.abs(n1-n2);
        if(n1>n2)
        {
            for(int i=0;i<diff;i++)
                head1=head1.next;
        }
        if(n2>n1)
        {
            for(int i=0;i<diff;i++)
                head2=head2.next;
        }
        while(head1!=null && head2!=null)
        {
            if(head1==head2)
                return head1;
            head1=head1.next;
            head2=head2.next;
        }
        return null;
    }

// Calculating size of linked list
    public int size(Node A)
    {
        int count=0;
        while(A!=null)
        {
          count++;
            A=A.next;
        }
        return count;
    }
}
Copy code

Time complexity: Traversing both linked lists to find the size + Traversing to find the intersecting node —> O(M+N) where M is the size of list1 and N is the size of list2.

Space complexity: No extra space —-> O(1)

Also Read: Priority Queue

9. Remove duplicates from sorted list

Problem Statement:

Given head of sorted linked list, remove duplicates such that each element appears only once and return sorted list with no duplicates.

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

Output format: [1, 2]

Input format: head=[1, 1, 2, 3, 3]

Output format: [1, 2, 3]

Approach:

Since the list is sorted, compare the current node’s data to next node’s data. If both are same, point current node’s next to next node’s next node.

Java function code:

public class Solution {
    public Node deleteDuplicates(Node A) {
        Node temp=A;
        while(temp!=null)
        {
            if(temp.next!=null && temp.val==temp.next.val)
            {
                if(temp==A)
                {
                    A=A.next;
                    temp=A;
                    continue;
                }
                else
                temp.next=temp.next.next;
            }
            else
            temp=temp.next;
        }
      return A;
    }
}
Copy code

Time complexity: Traversing linked list once —> O(N) where N is the size of linked list.

Space complexity: Only one extra node —-> O(1)

10. Linked List cycle

Given head of a linked list, return the node from where the cycle begins else return null.

Input format: head=[3, 2, 0, -4], pos=1

Output format: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node.

Input format: head=[1], pos=-1

Output format: false

Explanation: There is no cycle in the linked list.

Java function code:

public class Solution {
    public Node detectCycle(Node head) {
       Node slow=head;
       Node fast=head;
       while(fast.next!=null && fast.next.next!=null)
       {
           slow=slow.next;
           fast=fast.next.next;
           if(slow==fast)
           {
               fast=head;
               while(slow!=fast)
             {
              slow=slow.next;
              fast=fast.next;
             }
             return slow;
           }
           
       }   
       return null;
    }
}
Copy code

Time complexity: Traversing linked list —> O(N) where N is the size of linked list.

Space complexity: No extra space —-> O(1)

Must Read: 8 Most Important Data Structure Every Programmer Must Know

Conclusion

In this article, we have discussed top 10 practice problem of linked list in python.

Hope this article, will help to learn more about how to use linked list in Python.

Contributed By: Juhi Priya

Interview Questions

About the Author

Shiksha Online

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

Practice Problems of Linked List

1. Design and implement Linked List

2. Convert Binary Number in a Linked List to Integer

3. Delete node in linked list

4. Delete N Nodes After M Nodes of a Linked List

5. Middle element of linked list

6. Reverse linked list

7. Merge two sorted lists

8. Intersection of two Linked List cycle

9. Remove duplicates from sorted list

10. Linked List cycle

Conclusion

Top Picks & New Arrivals