1. You are given the head of a singly linked list.

Your task is to determine if the linked list

contains a loop. A loop exists in a linked list if the next pointer of the last node points to
any other node in the list (including itself), rather than being null.
Custom Input format:
A head of a singly linked list and a pos (1-based index) which denotes the position of the node
to which the last node points to. If pos = 0, it means the last node points to null, indicating there
is no loop.
Examples:
Input: head: 1 -> 3 -> 4, pos = 2
Output: true
Explanation: There exists a loop as last node is connected back to the second node.

Input: head: 1 -> 8 -> 3 -> 4, pos = 0

Output: false
Explanation: There exists no loop in given linked list.

Input: head: 1 -> 2 -> 3 -> 4, pos = 1

Output: true
Explanation: There exists a loop as last node is connected back to the first node.

Constraints:
1 ≤ number of nodes ≤ 104
1 ≤ node->data ≤ 103
0 ≤ pos ≤ Number of nodes in Linked List

Solution:
class Solution
{
static class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

public static boolean detectLoop(Node head)

{
Node slow = head;
Node fast = head;

while (fast != null && fast.next != null)

{
slow = slow.next; // Move slow by one
fast = fast.next.next; // Move fast by two

if (slow == fast)
{
return true; // Loop detected
}
}

return false; // No loop

}
}
public class Main {
public static void main(String[] args) {
Solution.Node head = new Solution.Node(1);
head.next = new Solution.Node(2);
head.next.next = new Solution.Node(3);
head.next.next.next = new Solution.Node(4);
head.next.next.next.next = head.next; // Creating a loop
System.out.println(Solution.detectLoop(head)); // Output: true
}
}
Given the head of a linked list, the task is to find the middle. For example, the middle of 1-> 2-
>3->4->5 is 3. If there are two middle nodes (even count), return the second middle. For
example, middle of 1->2->3->4->5->6 is 4.
Examples:
Input: Linked list: 1->2->3->4->5
Output: 3

Explanation: The given linked list is 1->2->3->4->5 and its middle is 3.

Input: Linked list: 2->4->6->7->5->1
Output: 7

Explanation: The given linked list is 2->4->6->7->5->1 and its middle is 7.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= no. of nodes <= 105
Solution:
class Solution
{
int getMiddle(Node head)
{
if (head == null)
return -1;

Node slow = head;

Node fast = head;

while (fast != null && fast.next != null)

{
slow = slow.next;
fast = fast.next.next;
}

return slow.data;

}
}
Given the head of a linked list, the task is to reverse this list and return the reversed head.
Examples:
Input: head: 1 -> 2 -> 3 -> 4 -> NULL
Output: 4 3 2 1
Explanation:

Input: head: 2 -> 7 -> 10 -> 9 -> 8 -> NULL

Output: 8 9 10 7 2
Explanation:

Input: head: 2 -> NULL

Output: 2
Explanation:

Constraints:
1 ≤ list.size, node->data ≤ 105
Solution:
class Solution
{
Node reverseList(Node head)
{
Node prev = null;
Node curr = head;
Node next = null;

while (curr != null)

{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;

}
}

Given a head singly linked list of positive integers. You have to check if the given linked list is
palindrome or not.

Examples:

Input: head: 1 -> 2 -> 1 -> 1 -> 2 -> 1

Output: true
Explanation: The given linked list is 1 -> 2 -> 1 -> 1 -> 2 -> 1 , which is a palindrome and
Hence, the output is true.

Input: head: 1 -> 2 -> 3 -> 4

Output: false
Explanation: The given linked list is 1 -> 2 -> 3 -> 4, which is not a palindrome and Hence, the
output is false.

Constraints:
1 ≤ number of nodes ≤ 105
1 ≤ node->data ≤ 103
Solution:
class Solution
{
public boolean isPalindrome(Node head)
{
if (head == null || head.next == null) return true;
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
Node secondHalf = reverseList(slow.next);
Node firstHalf = head;
Node temp = secondHalf;
boolean isPalindrome = true;
while (temp != null)
{
if (firstHalf.data != temp.data)
{
isPalindrome = false;
break;
}
firstHalf = firstHalf.next;
temp = temp.next;
 }
slow.next = reverseList(secondHalf);
return isPalindrome;
}
private Node reverseList(Node head)
{
Node prev = null;
Node curr = head;
while (curr != null)
{
Node nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
}

Given the head of a Singly Linked List and a value x, insert that value x at the end of the
LinkedList and return the modified Linked List.

Examples :

Input: LinkedList: 1->2->3->4->5 , x = 6

Output: 1->2->3->4->5->6
Explanation:

We can see that 6 is inserted at the end of the linkedlist.

Input: LinkedList: 5->4 , x = 1
Output: 5->4->1
Explanation:

We can see that 1 is inserted at the end of the linkedlist.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
0 <= number of nodes <= 105
1 <= node->data , x <= 103
Solution:
class Solution
{
public Node insertAtEnd(Node head, int x)
{
Node newNode = new Node(x);
if (head == null)
{
return newNode;
}
Node current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode;
return head;
}
}

Given the head a linked list, the task is to reverse every k node in the linked list. If the number
of nodes is not a multiple of k then the left-out nodes in the end, should be considered as a group
and must be reversed.
Examples:
Input: head = 1 -> 2 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8, k = 4
Output: 4 -> 2 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5

Explanation: The first 4 elements 1, 2, 2, 4 are reversed first and then the next 4 elements 5, 6,
7, 8. Hence, the resultant linked list is 4 -> 2 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5.
Input: head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 5 -> 4

Explanation: The first 3 elements 1, 2, 3 are reversed first and then left out elements 4, 5 are
reversed. Hence, the resultant linked list is 3 -> 2 -> 1 -> 5 -> 4.
Constraints:
1 <= size of linked list <= 105
1 <= data of nodes <= 106
1 <= k <= size of linked list
Solution:
class Solution
{

public Node reverseKGroup(Node head, int k)

{
if (head == null || k <= 1) return head;
Node current = head;
Node prev = null;
Node next = null;
int count = 0;
Node temp = head;
while (temp != null && count < k)
{
temp = temp.next;
 count++;
}
if (count == k)
{
current = head;
count = 0;
while (current != null && count < k)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
if (next != null)
{
head.next = reverseKGroup(next, k);
}
return prev;
}
else
{
current = head;
prev = null;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}
}
Given the head of two sorted linked lists consisting of nodes respectively. The task is
to merge both lists and return the head of the sorted merged list.

Examples:

Input: head1 = 5 -> 10 -> 15 -> 40, head2 = 2 -> 3 -> 20

Output: 2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40
Explanation:

Input: head1 = 1 -> 1, head2 = 2 -> 4

Output: 1 -> 1 -> 2 -> 4
Explanation:

Constraints:
1 <= list1.size, list2.size <= 103
0 <= node->data <= 105
Solution:
class Solution
{
Node sortedMerge(Node head1, Node head2)
{
Node dummy = new Node(0);
Node tail = dummy;
while (head1 != null && head2 != null)
{
if (head1.data <= head2.data)
{
tail.next = head1;
head1 = head1.next;
}
else
{
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
 }
if (head1 != null)
{
tail.next = head1;
}
else
{
tail.next = head2;
}
return dummy.next;
}
}
Given the head, the head of a singly linked list, Returns true if the linked list is circular
& false if it is not circular.
A linked list is called circular if it is not NULL terminated and all nodes are connected in the
form of a cycle.
Note: The linked list does not contain any inner loop.
Examples:
Input:

Output: true
Explanation: As shown in figure the first and last node is connected, i.e. 5 --> 2

Input:

Output: false
Explanation: As shown in figure this is not a circular linked list.
Constraints:
1 <= number of nodes <= 100
1 <= node -> data <= 104

Solution:
class Solution
{
static class Node {
 int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}

boolean isCircular(Node head)

{
if (head == null)
return true; // Empty list is considered circular

Node temp = head.next;

while (temp != null && temp != head) {

temp = temp.next;
}

return (temp == head); // true if we looped back to head

}
}
public class Main {
public static void main(String[] args) {
Solution.Node head = new Solution.Node(1);
Solution.Node second = new Solution.Node(2);
Solution.Node third = new Solution.Node(3);

head.next = second;
second.next = third;
third.next = head; // Makes it circular

Solution sol = new Solution();

System.out.println(sol.isCircular(head)); // Output: true
}
}
Given a singly linked list, your task is to remove every kth node from the linked list.
Examples:
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8, k = 2
Output: 1 -> 3 -> 5 -> 7
Explanation: After removing every 2nd node of the linked list, the resultant linked list will be: 1
-> 3 -> 5 -> 7.
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10, k = 3
Output: 1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 10

Explanation: After removing every 3rd node of the linked list, the resultant linked list will be: 1
-> 2 -> 4 -> 5 -> 7 -> 8 -> 10.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= size of linked list <= 106
1 <= node->data <= 106
1 <= k <= size of linked list

Solution:
class Solution
{
Node deleteK(Node head, int k)
{
if (head == null || k == 0)
return head;

if (k == 1)
return null; // Delete all nodes

Node curr = head;

int count = 1;

while (curr != null && curr.next != null) {

if (count == k - 1) {
// Skip k-th node
curr.next = curr.next.next;
count = 1;
curr = curr.next; // 🛠️move curr forward after deletion
 } else {
curr = curr.next;
count++;
}
}

return head;
}
}
Given a singly linked list and a number k. Find the (n/k)th element, where n is the number of
elements in the linked list. We need to consider ceil value in case of decimals.
Examples:
Input: LinkedList: 1->2->3->4->5->6 , k = 2
Output: 3
Explanation: 6/2th element is the 3rd(1-based indexing) element which is 3.

Input: 2->7->9->3->5 , k = 3
Output: 7
Explanation: The 5/3rd element is the 2nd element as mentioned in the question that we need to
consider ceil value in the case of decimals. So 2nd element is 7.

Constraints:
1 <= number of nodes <= 104
1 <= k <= number of nodes
1 ≤ node->data ≤ 103
Solution:
class Solution
{
public static int fractional_node(Node head, int k)
{
if (head == null || k <= 0) return -1;
int count = 0;
Node temp = head;
while (temp != null)
{
count++;
 temp = temp.next;
}
int index = (int) Math.ceil((double) count / k);
temp = head;
for (int i = 1; i < index; i++)
{
if (temp != null) temp = temp.next;
}
return temp != null ? temp.data : -1;
}
}
Given a linked list, you have to perform the following task:
1. Extract the alternative nodes starting from the second node.
2. Reverse the extracted list.
3. Append the extracted list at the end of the original list.
Note: Try to solve the problem without using any extra memory.
Examples:
Input: LinkedList: 10->4->9->1->3->5->9->4
Output: 10->9->3->9->4->5->1->4

Explanation: Alternative nodes in the given linked list are 4,1,5,4. Reversing the alternative
nodes from the given list, and then appending them to the end of the list results in a list 10->9-
>3->9->4->5->1->4.
Input: LinkedList: 1->2->3->4->5
Output: 1->3->5->4->2

Explanation: Alternative nodes in the given linked list are 2 and 4. Reversing the alternative
nodes from the given list, and then appending them to the end of the list results in a list of 1->3-
>5->4->2.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraints:
1 <= size of linked list <= 106
0 <= Node_value <= 109
Solution:
class Solution
{
 public static void rearrange(Node head)
{
if (head == null || head.next == null || head.next.next == null)
return;
Node odd = head;
Node even = head.next;
Node evenHead = even;
while (even != null && even.next != null)
{
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
Node prev = null;
Node curr = evenHead;
Node next = null;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
odd.next = prev;
}
}
Given two singly linked lists, write a program to get the point where two linked lists intersect
each other. If the linked list does not merge at any point, it should return -1.
Examples:
Input: LinkedList1: 3->6->9->common, LinkedList2: 10->common, common: 15->30->NULL
Output: 15
Explanation:
Input: LinkedList1: 4->1->common, LinkedList2: 5->6->1->common, common: 8->4->5-
>NULL
Output: 8
Explanation:

Expected Time Complexity: O(n+m)

Expected Space Complexity: O(n)
Constraints:
Length of Both LinkedList before the intersection(if any) is greater than 0.
1 ≤ no. of nodes in LinkedList1, LinkedList2 ≤ 105
-1000 ≤ node->data ≤ 1000
Challenge: Try to solve the problem without using any extra space.

Solution:
class Solution
{
Node intersectPoint(Node head1, Node head2)
{
int len1 = getLength(head1);
int len2 = getLength(head2);
int diff = Math.abs(len1 - len2);
if (len1 > len2)
{
for (int i = 0; i < diff; i++)
{
head1 = head1.next;
}
}
else
{
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;
}
int getLength(Node head)
{
int length = 0;
while (head != null)
{
length++;
head = head.next;
}
return length;
}
}