# Placement Practice | Linked Lists

In this blog, we will discuss Linked Lists, but in this blog, *we will discuss only major problems.*

*Linked Lists are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to each other using pointers.*

We have already covered some topics like already

Reverse a Linked Lists

**Problem: **We have given a pointer to the head node of the Linked list, the task is to reverse the list. We need to reverse the list by changing the links between nodes. It can be interpreted as:

```
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL
```

There can be three types of solutions to this problem, al of them are discussed here.

**Three-Pointers Solution:**

We will be using three-pointers **prev**, **curr**, and **next **to reverse the list. The below image is for only representative purposes.

**Pseudo Code:**

`void reverse(Node* `**head**)
{
// Initialize pointers
Node ***curr **= **head**;
Node ***prev **= NULL, ***next **= NULL
while (**curr **!= NULL)
{
**next **= **current**->**next**
**current**->**next **= **prev**
**prev **= **current**
**current **= **next**
}
**head **= **prev **
}

**Two Pointers Solution: **

We will be using auxiliary two pointers **curr**** **and** next **to reverse the links of the linked list. This is a little bit tricky solution. Try out with examples-

**Pseudo Code:**

`void reverse(Node* `**head**)
{
// Initialize pointers
Node ***current **= **head**;
Node ***prev **= NULL, *next = NULL
while (**current **!= NULL)
{
**next **= **current**->**next**
**current**->**next **= **prev**
**prev **= **current**
**current **= next
}
**head **= **prev **
}

**Recursive Solution:**

In this approach what we are trying to do is that we are making the previous node of the current node as his next node to reverse the linked list by passing a single pointer.

We return the pointer of the next node to his

**previous**(**current**) node and then make the**previous**node as the next node of the returned node and then returning the**current**node.We first traverse till the last node and making the last node as the

**head**node of the reversed linked list and then applying the above procedure in a recursive manner.

**Pseudo Code**

`Node* reverse(Node* `**node**)
{
if (**node **== NULL) :
return NULL
if (**node**->**next **== NULL) :
**head **= **node**
return **node**
Node* **temp **= reverse(**node**->**next**)
**temp**->**next **= **node **
**node**->**next **= NULL
return **node**
}

Detect L

**oop in a Linked List**

**Problem: **We have to check whether a linked list has a loop or not.

The below diagram shows a linked list with a loop.

**1**** **-> **2** -> **3**
| |
** ****5**** **<-** ****4**

**Hashing Solution: **

Traverse the list one by one and keep putting the node addresses in a Hash Table.

At any point, if NULL is reached then return

**false**, and if next of current node points to any of the previously stored nodes in Hash then return**true**.

**Pseudo Code:**

```
bool detectLoop(Node* hs)
{
seen //HashMap
while (hs != NULL)
{
// If this node is already present
// in hashmap it means there is a cycle
if (seen.find(hs) == True)
return true
// If we are seeing the node for
// the first time, insert it in hash
seen.insert(hs)
hs = hs->next
}
return false
}
```

**Floyd’s Cycle-Finding Algorithm: **

This is the fastest method.

Traverse linked list using two pointers.

Move one pointer by one step and another pointer by two-step.

If these pointers meet at the same node then there is a loop.

If pointers do not meet then the linked list doesn’t have a loop.

**Pseudo Code:**

```
bool detectloop(Node* head)
{
Node *
```**slow **= head, ***fast **= head
while (**slow **&& **fast **&& **fast**->next)
{
**slow **= **slow**->next
**fast **= **fast**->next->next
if (**slow **== **fast**)
return true
}
return false
}

Find Intersection Point of Two Linked List

**Problem: **By some programming error, the end node of one linked list got linked to the second linked list, depicted below. Write a program to get the point where two of them merge.

```
A: a1 -> a2
->
c1 -> c2 -> c3
->
B: b1 -> b2 -> b3
```

The above diagram shows an example with two linked lists having 100 as an intersection point.

*/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/*
**public** **class** Solution {
**public** ListNode getIntersectionNode(ListNode headA, ListNode headB) {
**int** len1 = 0;
**int** len2 = 0;
ListNode p1=headA, p2=headB;
**if** (p1 == **null** || p2 == **null**)
**return** **null**;
**while**(p1 != **null**){
len1++;
p1 = p1.next;
}
**while**(p2 !=**null**){
len2++;
p2 = p2.next;
}
**int** diff = 0;
p1=headA;
p2=headB;
**if**(len1 > len2){
diff = len1-len2;
**int** i=0;
**while**(i<diff){
p1 = p1.next;
i++;
}
}**else**{
diff = len2-len1;
**int** i=0;
**while**(i<diff){
p2 = p2.next;
i++;
}
}
**while**(p1 != **null** && p2 != **null**){
**if**(p1.val == p2.val){
**return** p1;
}
p1 = p1.next;
p2 = p2.next;
}
**return** **null**;
}
}

This solution works in **O(m+n)** but requires additional information with each node. An alternative solution that doesn’t require modification to the basic data structure can be implemented using a hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in the hash then return the intersecting node.

Happy Coding!

Follow us on Instagram __@programmersdoor__

Join us on Telegram __@programmersdoor__

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.