# Practice Problems of Linked List

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.

### 1. Design and implement Linked List

Input format:

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

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

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

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="">Copy code```

### 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.

E.g.-

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

Output: 5

Explanation: (101)_2 = (5)_10

Output: 0

Approach:

1. Iterate through the non-empty linked list and retrieve digits from linked list.
2. 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)

### 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.

1. 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.

Output format: [4,5,9]

Approach:

1. Copy the data of next node to the given node.
2. 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)

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

Problem statement:

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.

1. 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.

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

Output format: [1, 5, 9]

Approach:

1. 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.
1. 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)

### 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).

Output format: [3, 4, 5]

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

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:

1. Traverse the entire linked list and find the number of nodes.
2. 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 1st 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)

Problem Statement:

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

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

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

Output format: [2, 1]

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.

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

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

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

Output format: [0]

1. 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)

### 8. Intersection of two Linked List cycle

Problem Statement:

Output format: 8

Explanation: The intersected node’s value is 8.

Output format: null

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

Approach: Two pointers

1. Calculate the size of both linked lists.
1. Find the difference between their lengths and start traversing the longer linked list from the start to difference i.e. (b-a).
2. 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)

### 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.

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

Output format: [1, 2]

1. 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)

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

1. 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.

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)