.png)
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->NULLThere 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 <- 4Hashing 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 -> b3The 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.
Comments