Important Questions on LinkedList
So In this post, I am going to discuss about few important questions related to Linked Lists with solutions.
In the last Post, I discussed about basics of LinkedList.
- Add an element to the LinkedList
So in the previous post, I showed the solution to add an element by doing iteration till the last and then adding it, It will increase the complexity, So, we can do the same thing by just maintaining an extra pointer which is the tail pointer.
package com.first.learndsa.linkedlist;
public class LinkedListAddWithTail {
Node head, tail;
int size;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public void addElementAtLast(int data) {
Node newNode = new Node(data);
//If there is no element in the likedlist then it will be null
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
//Maintain the size of ll as well
size++;
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public static void main(String[] args) {
LinkedListAddWithTail aa = new LinkedListAddWithTail();
aa.addElementAtLast(10);
aa.addElementAtLast(20);
aa.printList();
}
}2. Find the Size of LinkedList
For finding the size of LinkedList we can maintain one size variable and whenever a new node is added to LinkedList we can increase the size, like the above example, Apart from that there are Iterative and recursive ways to find the size of LinkedList.
public int sizeOfLinkedListIterative(LinkedListAddWithTail ll) {
int size = 0;
Node temp = ll.head;
while (temp != null){
size++;
temp = temp.next;
}
return size;
}
public int sizeOfLinkedListRecursive(Node head ) {
if (head == null){
return 0;
}
return 1+ sizeOfLinkedListRecursive(head.next);
}3. Reverse a LinkedList
For reversing a LinkedList we Just need to reverse the pointers of the list like below.
10 -> 20 -> 30 -> 40 ->50 -> NULL
NULL <-10 <- 20 <- 30 <- 40 <-50We will maintain three pointers to keep track of nodes, current, previous, and next.
public Node reverseLinkedList(Node head) {
Node prev = null;Node next = null;
Node current = head;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}In the first iteration, the above program makes a Node with 10 -> Null, and then in the next iteration, it will make the next node point to this previous node. This way it will update all the pointers.
4. Detect a Loop in a LinkedList
Detecting a loop in a linked list can be solved using multiple ways
One approach is to use an extra data structure like HashSet and iterate over List and check if the node is already visited then it means loop is detected.
boolean detectALoop(Node head) {
Set<Node> nodeSet = new HashSet<>();
Node temp = head;
while (temp != null) {
if (!nodeSet.add(temp)) {
System.out.println("loop detected!!!!!!!!!!!");
return true;
}
temp = temp.next;
}
return false;
}Another approach is by editing the Node structure, by adding an extra field (flag) in every node checking the value of it, and marking it as 1 if visited.
boolean detectALoopUsingAflag(Node head) {
Node temp = head;
while (temp != null) {
if (temp.flag == 1) {
System.out.println("loop detected!!!!!!!!!!!");
return true;
}
temp = temp.next;
temp.flag = 1;
}
return false;
}Another approach is Using the algorithm, which is Floyd's Cycle Finding Algorithm
In this algorithm, we use two pointers one is a fast pointer another is a slow pointer. The fast pointer moves twice as fast compared to the slow pointer.
boolean detectALoopUsingFloydCycleAlgorithm(Node head) {
Node fastPointer = head;
Node slowPointer = head;
int flag = 0;
while (fastPointer != null && slowPointer != null && fastPointer.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
if (fastPointer == slowPointer) {
System.out.println("loop detected!!!!!!!!!!!");
flag = 1;
return true;
}
}
return false;
}5. Check if a LinkedList is Palindrome.
To Check if a LinkedList is a palindrome or not we can use a Stack data structure, By using a loop we can compare the values.
public boolean checkPallindromeLinkedList(Node head) {
Node temp = head;
Node temp2 = head;
Stack<Integer> stack = new Stack<>();
while (temp != null) {
stack.push(temp.data);
temp = temp.next;
}
while (temp2 != null) {
if (stack.pop() != temp2.data) {
return false;
}
temp2 = temp2.next;
}
return true;
}5. Merge two sorted LinkedList.
So In this question, we will given two separate sorted linked lists, we need to merge them and create a new linked list. One approach will be to use a set and store all the elements in it by iterating and sorting the set and creating a new linked list. Another is by using two temp nodes.
public Node mergeTwoSortedLinkedList(Node head1, Node head2) {
//first apprach s to use a set and iterate over it add all the
// elements into that and sort it and then using a loop create a new list
Node result = new Node(0);
Node tail = result;
while (true) {
Node temp1 = head1;
Node temp2 = head2;
if (temp1 == null) {
tail.next = temp2;
break;
}
if (temp2 == null) {
tail.next = temp1;
break;
}
if (temp1.data < temp2.data) {
tail.next = new Node(temp1.data);
temp1 = temp1.next;
} else {
tail.next = new Node(temp2.data);
temp2 = temp2.next;
}
tail = tail.next;
}
return result.next;
}6. Remove Duplicates from the sorted LinkedList.
public void removeDuplicateFromSortedLinkedList(Node head) {
Node curr = head;
while (curr != null) {
Node temp = curr;
while (temp != null && temp.data == curr.data) {
temp = temp.next;
}
curr.next = temp;
curr = curr.next;
}
}7. Find the middle element of the LinkedList.
Since we are maintaining the size of the list as well, we can get mid by dividing by 2 of size, and then by traversing the list till half, we can return mid element.
Another approach will be maintaining two pointers fast and slow, fast will move by 2x and slow by 1x so once the fast pointer reaches to the end slow will be at mid.
public int middleOfTheLinkedList(Node head) {
int listSize = size;
int mid = size/2;
Node midNode = head;
for (int i = 0; i<mid;i++) {
midNode = midNode.next;
}
return midNode.data;
}// Maintain fast and slow pointer, fast will moe by 2x , so when it will at end
//slow will be at middle because slow is moving by 1x
public int middleOfTheLinkedListUsingTwoPointers(Node head) {
Node fastPtr = head;
Node slowPtr = head;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
}
return slowPtr.data;
}8. Add two numbers, represented as LinkedList.
For solving this problem we can use Math, first get the number formed using the first list then from the second, and construct a new one by adding them.
public Node addTwoNumbers(Node head1, Node head2) {
Node temp1 = head1;
Node temp2 = head2;
int n1= 0;
while (temp1 != null) {
n1 = n1*10 + temp1.data;
temp1 = temp1.next;
}
int n2= 0;
while (temp2 != null) {
n2 = n2*10 + temp2.data;
temp2 = temp2.next;
}
LinkedListAddWithTail l = new LinkedListAddWithTail();
int n3 = n1+n2;
while (n3 != 0) {
int digit = n3%10;
//Form a linkedlist
l.addElementAtLast(digit);
n3 = n3/10;
}
return l.head;
}So the above problems are a few of the Important LinkedList problems. Solving them will surely give confidence to solve other questions.
Follow me for more such content.
Thanks for reading!!
