# Practice Problems of Linked List

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**

**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\n <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="">\n length)\n return;\n if(position==1)\n head=head.next;\n else\n {\n int count=1;\n Node temp=head;\n while(count\n \n <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="">\n \n </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="">\n </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="">

**Must Read:** Circular Linked List

**2. ****Convert Binary Number in a Linked List to Integer**

**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; }}

**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**

**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 }}

**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; }}

**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;}

**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; }}

**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; }}

**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; }}

**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)*

**8. Intersection of two ****Linked List cycle**

**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; }}

**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; }}

**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; }}

**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**

Top Online Python Compiler | How to Check if a Python String is Palindrome | Feature Selection Technique | Conditional Statement in Python | How to Find Armstrong Number in Python | Data Types in Python | How to Find Second Occurrence of Sub-String in Python String | For Loop in Python |Prime Number | Inheritance in Python | Validating Password using Python Regex | Python List |Market Basket Analysis in Python | Python Dictionary | Python While Loop | Python Split Function | Rock Paper Scissor Game in Python | Python String | How to Generate Random Number in Python | Python Program to Check Leap Year | Slicing in Python

**Interview Questions**

Data Science Interview Questions | Machine Learning Interview Questions | Statistics Interview Question | Coding Interview Questions | SQL Interview Questions | SQL Query Interview Questions | Data Engineering Interview Questions | Data Structure Interview Questions | Database Interview Questions | Data Modeling Interview Questions | Deep Learning Interview Questions |

**About the Author**

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