Singly linked lists are versatile data structures that offer efficient insertion, deletion, and traversal operations. However, beyond the basic CRUD (Create, Read, Update, Delete) operations, there lies a realm of logical operations that can be performed on singly linked lists. In this detailed blog, we’ll explore some of the most important logical operations that can be applied to singly linked lists in Java, providing insights into their implementation and usage.

**How to search an element in a Singly Linked List in Java?**

**head –> 10 –> 8 –> 1 –> 11 –> null**

```
ListNode current = head;
while(current != null)
{
if(current.data == searchKey)
{
return true;
}
current = current.next;
}
return false;
```

As the main logic, we need to traverse the list node by node. While traversing, we check each node’s data. If it matches the search key, then we’ve found the key; otherwise, we haven’t found it.

- We create a temporary node
`current`

to traverse the list until the end. Initially, it’s set to the head node, i.e.,`ListNode current = head`

. - Using a while loop, we traverse until the end of the list. If
`current`

becomes null, it means we’ve reached the end, and we terminate the loop. During traversal, we check each node’s data with the search key. If we find a match, we return`true`

immediately and exit the loop.

```
while( current != null )
{
if(current.data == searchKey)
{
return true;
}
current = current.next; // Move to the next node in each iteration
}
```

- Finally, if we haven’t found the exact search key after traversing the entire list, we return
`false`

.

**Output:**

- If the search key is 1, then it is found.
- If the search key is 12, then it is not found.

**Code**

```
public boolean find(ListNode head, int searchKey) {
if (head == null) {
return false;
}
ListNode current = head;
while (current != null) {
if (current.data == searchKey) {
return true;
}
current = current.next; // Move to the next node
}
return false;
}
```

This method `find`

is designed to search for a specific key value (`searchKey`

) within the linked list. It returns `true`

if the key is found, and `false`

otherwise. If the list is empty (i.e., `head`

is null), it immediately returns `false`

. Otherwise, it traverses the list, comparing the data value of each node (`current.data`

) with the search key. If a match is found, it returns `true`

. If the end of the list is reached without finding the key, it returns `false`

.

**How to reverse a singly linked list in java**

**Input:**

head –> 10 –> 8 –> 1 — > 11 –> null

**Output:**

head –> 11 –> 1 –> 8 –> 10 –> null

```
ListNode current = head;
ListNode previous = null;
ListNode next = null;
while(current != null)
{
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
```

The main logic is to traverse the list until the end and apply a logic that reverses the pointing of each node. Ultimately, we obtain the reversed list.

- We create three temporary nodes:
`current`

points to`head`

.`previous`

initially points to`null`

.`next`

also initially points to`null`

.

- We traverse the list node by node using a while loop. The loop iterates until
`current`

becomes`null`

. - In each iteration of the while loop, we perform the following operations:

```
while(current != null)
{
next = current.next; // Store the reference to the next node
current.next = previous; // Reverse the pointing direction of the current node
previous = current; // Move forward: previous becomes current
current = next; // Move forward: current becomes next
}
```

- First, we move to the next node by assigning
`next`

to`current.next`

. - Second, we reverse the reference of the current node to point to the
`previous`

node. - Third, we update
`previous`

to be the`current`

node, preparing for the next iteration. - Finally, we move forward by assigning
`next`

to`current`

.

- First, we move to the next node by assigning
- When the while loop terminates, we have reversed the entire list, and the last
`previous`

node becomes the new head of the list. So, we return`previous`

.

**Output:** `head --> 11 --> 1 --> 8 --> 10 --> null`

.

After the reversal, the list becomes reversed.

**Code**

```
public ListNode reverse(ListNode head)
{
if(head == null)
{
return head;
}
ListNode current = head;
ListNode previous = null;
ListNode next = null;
while(current != null)
{
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
```

This method `reverse`

is designed to reverse the linked list. If the list is empty (i.e., `head`

is null), it immediately returns null. Otherwise, it iterates through the list, changing the next pointer of each node to point to the previous node. At the end of the iteration, it returns the last node encountered, which becomes the new head of the reversed list.

**How to find middle node in singly linked list in java ?**

To find the middle node in a singly linked list, we employ the same logic for two different cases.

**Case 1: List having an even number of nodes:**

For example, head –> 10 –> 8 –> 1 –> 11 –> null

In this case, the middle node is 1.

**Case 2:** **List having an odd number of nodes:**

For example, head –> 10 –> 8 –> 1 –> 11 –> 15 –> null

Here again, the middle node is 1.

```
ListNode slowPtr = head;
ListNode fastPtr = head;
while(fastPtr != null && fastPtr.next != null) {
slowPtr = slowPtr.next; // Move slow pointer to the next node
fastPtr = fastPtr.next.next; // Move fast pointer to two nodes ahead
}
return slowPtr; // Return the slow pointer, which points to the middle node
```

The main logic involves using two different pointers: a slow pointer and a fast pointer. The slow pointer moves to the next node one by one, while the fast pointer moves two nodes ahead at a time. When the fast pointer reaches the end (either pointing to null or its next points to null), the while loop terminates, and we return the slow pointer, which represents the middle node in both cases.

**Code**

```
public ListNode getMiddleNode() {
if (head == null) {
return null;
}
ListNode slowPtr = head;
ListNode fastPtr = head;
while (fastPtr != null && fastPtr.next != null) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
return slowPtr;
}
```

This method `getMiddleNode`

is designed to find and return the middle node of the linked list. It initializes two pointers, `slowPtr`

and `fastPtr`

, both starting at the head of the list. The `slowPtr`

moves one node at a time while the `fastPtr`

moves two nodes at a time. When the `fastPtr`

reaches the end of the list (or `null`

), the `slowPtr`

will be at the middle node. If the list is empty (i.e., `head`

is null), it returns null.

**How to detect a loop in Singly Linked List in java ?**

In a given singly linked list, if there exists a loop, it can be identified by employing the following logic.

Consider the linked list: **head –> 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 3**

As it can be seen, the list loops back to the node with value 3.

The main logic remains the same as before: we use two different pointers, a slow pointer and a fast pointer. However, in this case, we move the fast pointer first, followed by the slow pointer. Due to the loop, these pointers will eventually meet at the same node. Once the slow and fast pointers are equal, pointing to the same node, we can conclude that there exists a loop in the linked list. If the pointers never meet, then the list does not contain any loop.

```
ListNode fastPtr = head;
ListNode slowPtr = head;
while(fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next; // Move fast pointer two nodes ahead
slowPtr = slowPtr.next; // Move slow pointer one node ahead
if(slowPtr == fastPtr) { // If slow pointer meets fast pointer, it indicates a loop
return true;
}
}
return false; // If loop termination condition is met without meeting points, return false
```

The main logic is the same as before: we use two pointers, a slow pointer and a fast pointer, to traverse the list. However, in this case, we move the fast pointer two nodes ahead and the slow pointer one node ahead in each iteration. If the pointers meet at any point during traversal, it indicates the presence of a loop in the list, and we return true. If the loop termination condition is met without the pointers meeting, it means there is no loop in the list, and we return false.

**Code**

```
public boolean containsLoop() {
ListNode fastPtr = head;
ListNode slowPtr = head;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next; // We need to move fast pointer fast so that it will catch the slow pointer if a loop is present
slowPtr = slowPtr.next;
if (slowPtr == fastPtr) {
return true;
}
}
return false;
}
public void createALoopInLinkedList() {
ListNode first = new ListNode(1);
ListNode second = new ListNode(2);
ListNode third = new ListNode(3);
ListNode fourth = new ListNode(4);
ListNode fifth = new ListNode(5);
ListNode sixth = new ListNode(6);
head = first;
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
fifth.next = sixth;
sixth.next = third;
}
```

The method `containsLoop`

checks whether a loop exists in the linked list using Floyd’s Cycle Detection Algorithm. It initializes two pointers, `fastPtr`

and `slowPtr`

, both starting at the head of the list. The `fastPtr`

moves twice as fast as the `slowPtr`

. If there is a loop in the list, eventually, the `fastPtr`

will catch up with the `slowPtr`

. If no loop is found, the method returns false.

The method `createALoopInLinkedList`

is a helper method to create a loop in the linked list for testing purposes. It creates a linked list with six nodes and then creates a loop by making the next reference of the last node point to the third node.

**How to find nth node from the end of a Singly Linked List** **in java?**

Consider the singly linked list:

**head –> 10 –> 8 –> 1 –> 11 –> 15 –> null**

If we want to find the node that is “n” positions from the end of the list, where “n” is given as 2, then the node containing 11 would be that node.

```
ListNode mainPtr = head; // It will move forward when the reference pointer covers the nth position forward from the head
ListNode referencePtr = head; // It will move twice: first, it covers the nth distance from the head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position
int count = 0; // It is to track the number of nodes the reference pointer moved forward
while(count < n) {
refPtr = refPtr.next;
count++;
}
while(refPtr != null) {
refPtr = refPtr.next;
mainPtr = mainPtr.next;
}
return mainPtr;
```

The main logic involves using two pointers: a main pointer and a reference pointer. The reference pointer moves forward until it reaches the nth position from the head, while the main pointer remains stationary. After reaching the nth position, the reference pointer continues moving until it reaches the end of the list, while the main pointer moves along with it. When the reference pointer reaches the end of the list, the main pointer will be pointing to the nth node from the end of the list.

**Code**

```
public ListNode getNthNodeFromEnd(int n) {
if (head == null) {
return null;
}
if (n <= 0) {
throw new IllegalArgumentException("Invalid value: n = " + n);
}
ListNode mainPtr = head; // It will move forward when the reference pointer covers the nth position forward from the head
ListNode refPtr = head; // It will move twice: first, it covers nth distance from head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position.
int count = 0; // It is to track the number of nodes refPtr moved forward
while (count < n) {
if (refPtr == null) {
throw new IllegalArgumentException(n + " is greater than the number of nodes in the list");
}
refPtr = refPtr.next;
count++;
}
while (refPtr != null) {
refPtr = refPtr.next;
mainPtr = mainPtr.next;
}
return mainPtr; // The returned mainPtr will be at the nth position from the end of the list
}
```

This method `getNthNodeFromEnd`

is designed to find and return the nth node from the end of the linked list. It initializes two pointers, `mainPtr`

and `refPtr`

, both starting at the head of the list. The `refPtr`

moves forward `n`

positions from the head. Then, both pointers move forward simultaneously until the `refPtr`

reaches the end of the list. At this point, the `mainPtr`

will be at the nth node from the end. If the list is empty or if the value of `n`

is less than or equal to 0, the method throws an `IllegalArgumentException`

.

**How to remove duplicates from sorted Singly Linked List in java?**

For the given input of a sorted linked list:

**head –> 1 –> 1 –> 2 –> 3 –> 3 –> null**

The desired output is a sorted linked list with duplicates removed:

**head –> 1 –> 2 –> 3 –> null**

```
ListNode current = head;
while(current != null && current.next != null) {
if(current.data == current.next.data) {
current.next = current.next.next; // Connect current to the next next node to remove the duplicate node
} else {
current = current.next; // Move to the next node if no duplicate is found
}
}
```

The main logic involves traversing the list node by node using a current pointer. While traversing, we check whether the data of the current node is equal to the data of the next node. If they are equal, it means a duplicate node is found, so we connect the current node to the next next node, effectively removing the duplicate node between them. If no duplicate is found, we simply move to the next node. This process continues until we reach the end of the list or the current node becomes null.

**Code**

```
public void removeDuplicates() {
if (head == null) {
return;
}
ListNode current = head;
while (current != null && current.next != null) {
if (current.data == current.next.data) {
current.next = current.next.next;
} else {
current = current.next;
}
}
}
```

This method `removeDuplicates`

is designed to remove duplicates from a sorted linked list. It iterates through the list using the `current`

pointer. If the current node’s data is equal to the data of the next node, it skips the next node by updating the `next`

reference of the current node to skip the duplicate node. Otherwise, it moves the `current`

pointer to the next node in the list. If the list is empty (i.e., `head`

is null), the method returns without performing any operation.

**Now,** **How to insert a node in a sorted Singly Linked List in java?**

Given the sorted linked list:

**head –> 1 –> 8 –> 10 –> 16 –> null**

And a new node:

**newNode –> 11 –> null**

We want to insert the new node (11) into the sorted list such that the sorting order remains the same.

After insertion, the updated list would be:

**head –> 1 –> 8 –> 10 –> 11 –> 16 –> null**

```
ListNode current = head;
ListNode previous = null;
while(current != null && current.data < newNode.data) {
previous = current;
current = current.next;
}
// When we reach the insertion point, we have references to current, previous, and newNode.
// Now, we rearrange the pointers so that previous points to newNode and newNode points to current.
newNode.next = current;
if (previous != null) {
previous.next = newNode;
} else {
// If previous is null, it means the newNode should become the new head.
head = newNode;
}
return head;
```

The main logic involves traversing the sorted linked list until we find the appropriate position to insert the new node while maintaining the sorting order. We traverse the list node by node, comparing the data of each node with the data of the new node. We continue this process until we find a node whose data is greater than or equal to the data of the new node, or until we reach the end of the list.

When we reach the insertion point, we have references to three nodes: the current node, the previous node (the node before the insertion point), and the new node. To insert the new node into the list, we rearrange the pointers so that the previous node points to the new node, and the new node points to the current node.

If the previous node is null, it means that the new node should become the new head of the list. In this case, we update the head pointer to point to the new node.

**Code**

```
public ListNode insertInSortedList(int value) {
ListNode newNode = new ListNode(value);
if (head == null) {
return newNode;
}
ListNode current = head;
ListNode previous = null;
while (current != null && current.data < newNode.data) { // Will go till the end while checking the sorting order between the current node and the new node data
previous = current;
current = current.next;
}
// When we reach the insertion point, we have our current, previous, and newNode references so we only need to arrange pointers.
// So that previous will point to newNode and newNode will point to current.
newNode.next = current;
if (previous == null) { // If the new node is to be inserted at the beginning
head = newNode;
} else {
previous.next = newNode;
}
return head;
}
```

This method `insertInSortedList`

is designed to insert a new node with the provided value into a sorted linked list. If the list is empty (i.e., `head`

is null), the new node becomes the head of the list. Otherwise, it traverses the list to find the correct position to insert the new node while maintaining the sorted order. Once the insertion point is found, it updates the pointers to insert the new node. Finally, it returns the head of the list.

**How to remove a given key from singly linked list in java?**

Given the linked list:

**head –> 1 –> 8 –> 10 –> 11 –> 16 –> null**

Suppose our key is **11**, and we want to remove it from the list.

After removal, the updated list would be:

**head –> 1 –> 8 –> 10 –> 16 –> null**

```
ListNode current = head;
ListNode previous = null;
// Traverse the list to find the node with the key value
while(current != null && current.data != key) {
previous = current;
current = current.next;
}
// If we reached the end of the list without finding the key, return
if(current == null) {
return;
}
// If we found the key, remove the node by adjusting the previous node's next reference
if(previous != null) {
previous.next = current.next;
} else {
// If the key is found at the head, update the head pointer to skip the current node
head = current.next;
}
```

The main logic involves traversing the linked list until we find the node with the specified key value. While traversing, we keep track of the previous node as well.

If we reach the end of the list without finding the key, it means the key doesn’t exist in the list, so we return without performing any removal.

If we find the node with the key value, we remove it from the list by adjusting the next reference of the previous node to skip over the current node. However, if the key is found at the head of the list, we update the head pointer to skip over the current node.

**Code**

```
public void deleteNode(int key) {
ListNode current = head;
ListNode previous = null;
// If we find our key at the first node that is head, just update head to point to the next node.
if (current != null && current.data == key) {
head = current.next;
return;
}
while (current != null && current.data != key) {
previous = current;
current = current.next;
}
// If we reached the end of the list (current == null), the key was not found, so return without performing any operation.
if (current == null) {
return;
}
// If we found the key, update the next reference of the previous node to point to the next node of the current node, effectively removing the current node.
previous.next = current.next;
}
```

This method `deleteNode`

is designed to delete a node with the given key value from the linked list. It iterates through the list using the `current`

pointer to find the node with the specified key value while keeping track of the previous node using the `previous`

pointer. If the key is found at the first node (head), it updates the head to point to the next node. If the key is found in the middle of the list, it updates the next reference of the previous node to skip the current node. If the key is not found in the list, the method simply returns without performing any operation.

**Bonus: Two Sum Problem in java**

**Problem:** Given an array of integers, return the indices of the two numbers such that they add up to a specific target.

**Example:** Given array of integers: **{2, 11, 5, 10, 7, 8}**, and **target = 9**.

**Solution:** Since arr[0] + arr[4] = 2 + 7 = 9, we return {0, 4} as the indices.

The main logic involves using a map for fast lookup of stored values to find the exact sum of the target. We require one map for lookup purposes and one result array to store the indices of the two numbers that add up to the target sum from the given array. Here’s how it works:

- We iterate through the array, examining each element.
- At each element, we calculate the difference between the target and the current element.
- We check if this difference exists in the map. If it does, it means we have found the two numbers that add up to the target.
- We return the indices of the current element and the element with the required difference.
- If the difference is not found in the map, we store the current element’s value along with its index in the map for future lookups.

**Algorithm & Executions**

```
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < numbers.length; i++) {
int complement = target - numbers[i];
if(map.containsKey(complement)) {
result[0] = map.get(complement);
result[1] = i;
return result;
}
map.put(numbers[i], i);
}
return result;
```

The main logic involves using a hash map to store the indices of elements in the array. We traverse the array and, for each element, check if its complement (target – current number) exists in the hash map. If it does, it means we have found two numbers that add up to the target, so we return their indices. If not, we add the current number and its index to the hash map for future reference.

**Code**

```
public static int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (!map.containsKey(target - numbers[i])) {
map.put(numbers[i], i);
} else {
result[1] = i;
result[0] = map.get(target - numbers[i]);
return result;
}
}
throw new IllegalArgumentException("Two numbers not found");
}
```

This method `twoSum`

is designed to find and return the indices of the two numbers in the `numbers`

array that add up to the `target`

value. It utilizes a hashmap to store the difference between the target and each element of the array along with its index. It iterates through the array, checking if the hashmap contains the difference between the target and the current element. If not, it adds the current element and its index to the hashmap. If it finds the difference in the hashmap, it retrieves the index of the other number and returns the indices as the result. If no such pair of numbers is found, it throws an `IllegalArgumentException`

.

**Note: Why is this Array Manipulation problem being discussed here?**

While the problem of finding two numbers in an array that add up to a specific target is not directly related to singly linked list operations, the underlying logic and problem-solving techniques used in solving array manipulation problems can indeed be helpful in solving problems related to singly linked lists.

Many problem-solving techniques and algorithms used in array manipulation, such as iterating over elements, using hash maps for fast lookups, or employing two-pointer approaches, can also be applied to singly linked list problems. Additionally, understanding how to efficiently manipulate data structures and analyze patterns in data is a fundamental skill that can be transferred across various problem domains.

In the context of computer science and algorithmic problem-solving, building a strong foundation in problem-solving techniques through various types of problems, including those involving arrays, linked lists, trees, graphs, and more, can enhance your ability to tackle a wide range of problems effectively.

So, while the specific problem discussed may not directly relate to singly linked lists, the problem-solving skills and techniques learned from array manipulation problems can certainly be beneficial in solving problems related to singly linked lists and other data structures.

**Conclusion**

By mastering the logical operations of singly linked list in Java, programmers can unlock the full potential of this versatile data structure. Whether it’s searching, reversing, merging, or detecting loops, understanding these operations equips developers with powerful tools for solving complex problems and building efficient algorithms. With the insights provided in this blog, programmers can elevate their skills and become more proficient in leveraging singly linked lists for various applications.