# Problems based on Linked List

Let us see a few problems based on Linked List.

Given a linked list of N nodes such that it may contain a loop.

A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0.

Remove the loop from the linked list, if it is present, i.e. unlink the last node forming the loop.

Example:

```Input:
N = 3
value[] = {1,3,4}
X = 2
Output: 1
Explanation: The link list looks like
1 -> 3 -> 4
^    |
|____|
A loop is present. If you remove it
successfully, the answer will be 1.```

Solution:

``````class Solution
{
//Function to remove a loop in the linked list.
// code here

// Detect loop using Floyd's algorithm
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}

// If loop exists, find the start of the loop
if (slow == fast) {
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}
// Remove the loop by setting the next pointer of the last node in the loop to null
fast.next = null;
}

}
}``````

Time Complexity: O(n)

Space Complexity: O(1)

The steps involved:

1. Detect the loop in the linked list using Floyd’s algorithm. When the slow and fast pointers meet, it means there is a loop in the linked list.
2. Once the loop is detected, initialize either the slow or the fast pointer to the head of the linked list.
3. Now, move both pointers one node at a time until they meet. The node where they meet is the start of the loop.
4. To remove the loop, set the next pointer of the node where the fast pointer met the slow pointer to null.

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Example:

```Input:
N = 2
Output: 8
Explanation: In the first example, there
are 9 nodes in linked list and we need
to find 2nd node from end. 2nd node
from end is 8.  ```

Solution:

``````class Solution
{
//Function to find the data of nth node from the end of a linked list.
{

// Move the fast pointer N nodes ahead of the slow pointer
for (int i = 0; i < N; i++) {
if (fast == null) {
// The length of the linked list is less than N
return -1;
}
fast = fast.next;
}

// Move both pointers together until the fast pointer reaches the end of the linked list
while (fast != null) {
slow = slow.next;
fast = fast.next;
}

// At this point, the slow pointer will be pointing to the Nth node from the end of the linked list
return slow.data;

}
}
``````

Time Complexity: O(n)

Space Complexity: O(1)

The two-pointer method can be used to find the Nth node from the end of a linked list.

• We keep two pointers on hand, one slow and one quick. Initially, both pointers point to the linked list’s head node.
• The fast pointer is moved N nodes ahead of the slow pointer.
• The points are then moved together until the fast pointer reaches the end of the linked list.
• The slow pointer will now point to the Nth node from the end of the linked list.
• If the linked list’s length is less than N, we return -1.

Given a singly linked list of size N of integers. The task is to check if the given linked list is palindrome or not.

Example:

```Input:
N = 3
value[] = {1,2,1}
Output: 1
Explanation: The given linked list is
1 2 1 , which is a palindrome and
Hence, the output is 1.```

Solution:

``````class Solution
{
//Function to check whether the list is palindrome.
{
Stack<Integer> stack = new Stack<Integer>();

// Traverse the linked list and push all elements onto the stack
while (current != null) {
stack.push(current.data);
current = current.next;
}

// Traverse the linked list again and compare with the popped element
while (current != null) {
if (current.data != stack.pop()) {
return false;
}
current = current.next;
}
return true;
}
}``````

Time Complexity: O(n)

Space Complexity: O(n)

In this code, we used a stack to hold all the linked list elements. We traversed the linked list twice: first to push all the elements onto the stack and again to pop each element from the stack and compare it to the value of the current node. The linked list is a palindrome if all the components match.

Given a singly linked list of N nodes.
The task is to find the middle of the linked list. For example, if the linked list is
1-> 2->3->4->5,then the middle node of the list is 3.
If there are two middle nodes(in case, when N is even), print the second middle element.
For example, if the linked list given is 1->2->3->4->5->6, then the middle node of the list is 4.

Example:

```Input:
Output: 3
Explanation:
Middle of linked list is 3.```

Solution:

``````class Solution
{
{

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

return slow.data;
}
}
``````

Time Complexity: O(n)

Space Complexity: O(1)

In this implementation, we use two pointers `slow` and `fast` to traverse the linked list. `slow` moves one node at a time, while `fast` moves two nodes at a time. When `fast` reaches the end of the list, `slow` will be pointing to the middle node. If the length of the list is even, then `slow` will be pointing to the second middle node.

We initialize both `slow` and `fast` to the head of the list, and then we iterate through the list as long as `fast` is not null and `fast.next` is not null. In each iteration, we move `slow` one step forward and `fast` two steps forward. When the loop terminates, `slow` will be pointing to the middle node.

Finally, we return the middle node.