Implement a stack using singly linked list
To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to perform Pop , Push , Peek ,Display operations in the following article .
A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.
The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.
Stack Operations:
- push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
- pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
- peek(): Return the top element.
- display(): Print all elements in Stack.
Below is the implementation of the above approach:
|
// C++ program to Implement a stack
//using singly linked list
#include <bits/stdc++.h>
using namespace std;
// Declare linked list node
struct Node
{
int data;
Node* link;
};
Node* top;
// Utility function to add an element
// data in the stack insert at the beginning
void push(int data)
{
// Create new node temp and allocate memory in heap
Node* temp = new Node();
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp)
{
cout << "\nStack Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
int isEmpty()
{
//If top is NULL it means that
//there are no elements are in stack
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// If stack is not empty , return the top element
if (!isEmpty())
return top->data;
else
exit(1);
}
// Utility function to pop top
// element from the stack
void pop()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
// Assign top to temp
temp = top;
// Assign second node to top
top = top->link;
//This will automatically destroy
//the link between first node and second node
// Release memory of top node
//i.e delete the node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
temp = top;
while (temp != NULL)
{
// Print node data
cout << temp->data << "-> ";
// Assign temp link to temp
temp = temp->link;
}
}
}
// Driver Code
int main()
{
// Push the elements of stack
push(11);
push(22);
push(33);
push(44);
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
// Delete top elements of stack
pop();
pop();
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
return 0;
}
|
|
// Java program to Implement a stack
// using singly linked list
// import package
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data; // integer data
Node link; // reference variable Node type
}
// create global top reference variable global
Node top;
// Constructor
StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add an element x in the stack
public void push(int x) // insert at the beginning
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Utility function to return top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
// update the top pointer to point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
while (temp != null) {
// print node data
System.out.printf("%d->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class GFG {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}
|
|
'''Python supports automatic garbage collection so deallocation of memory
is done implicitly. However to force it to deallocate each node after use,
add the following code:
import gc #added at the start of program
gc.collect() #to be added wherever memory is to be deallocated
'''
class Node:
# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# head is default NULL
def __init__(self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
# adds to the start of the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head (start of the stack)
def pop(self):
if self.isempty():
return None
else:
# Removes the head node and makes
#the preceding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
# Returns the head node data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
# Prints out the stack
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
# Driver code
MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(33)
MyStack.push(44)
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ",MyStack.peek())
# Delete top elements of stack
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ", MyStack.peek())
# This code is contributed by Mathew George
|
|
// C# program to Implement a stack
// using singly linked list
// import package
using System;
// Create Stack Using Linked list
public class StackUsingLinkedlist
{
// A linked list node
private class Node
{
// integer data
public int data;
// reference variable Node type
public Node link;
}
// create global top reference variable
Node top;
// Constructor
public StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add
// an element x in the stack
// insert at the beginning
public void push(int x)
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full.
// Then inserting an element
// would lead to stack overflow
if (temp == null)
{
Console.Write("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if
// the stack is empty or not
public bool isEmpty()
{
return top == null;
}
// Utility function to return
// top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty())
{
return top.data;
}
else
{
Console.WriteLine("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
// update the top pointer to
// point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
else
{
Node temp = top;
while (temp != null)
{
// print node data
Console.Write("{0}->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// Driver code
public class GFG
{
public static void Main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
}
}
// This code is contributed by 29AjayKumar
|
|
<script>
// Javascript program to Implement a stack
// using singly linked list
// import package
// A linked list node
class Node
{
constructor()
{
this.data=0;
this.link=null;
}
}
// Create Stack Using Linked list
class StackUsingLinkedlist
{
constructor()
{
this.top=null;
}
// Utility function to add an element x in the stack
push(x)
{
// create new node temp and allocate memory
let temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
document.write("<br>Heap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = this.top;
// update top reference
this.top = temp;
}
// Utility function to check if the stack is empty or not
isEmpty()
{
return this.top == null;
}
// Utility function to return top element in a stack
peek()
{
// check for empty stack
if (!this.isEmpty()) {
return this.top.data;
}
else {
document.write("Stack is empty<br>");
return -1;
}
}
// Utility function to pop top element from the stack
pop() // remove at the beginning
{
// check for stack underflow
if (this.top == null) {
document.write("<br>Stack Underflow");
return;
}
// update the top pointer to point to the next node
this.top = this.top.link;
}
display()
{
// check for stack underflow
if (this.top == null) {
document.write("<br>Stack Underflow");
}
else {
let temp = this.top;
while (temp != null) {
// print node data
document.write(temp.data+"->");
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
// create Object of Implementing class
let obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
document.write("<br>Top element is ", obj.peek()+"<br>");
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
document.write("<br>Top element is ", obj.peek()+"<br>");
// This code is contributed by rag2127
</script>
|
Output:
44->33->22->11-> Top element is 44 22->11-> Top element is 22
Time Complexity:
The time complexity for all push(), pop(), and peek() operations is O(1) as we are not performing any kind of traversal over the list. We perform all the operations through the current pointer only.
Find first node of loop in a linked list
Write a function findFirstLoopNode() that checks whether a given Linked List contains a loop. If the loop is present then it returns point to the first node of the loop. Else it returns NULL.
Example :
Input : Head of below linked listOutput : Pointer to node 2We have discussed Floyd’s loop detection algorithm. Below are steps to find the first node of the loop.
1. If a loop is found, initialize a slow pointer to head, let fast pointer be at its position.
2. Move both slow and fast pointers one node at a time.
3. The point at which they meet is the start of the loop.
|
// C++ program to return first node of loop.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
// Function to detect and remove loop
// in a linked list that may contain loop
Node* detectAndRemoveLoop(Node* head)
{
// If list is empty or has only one node
// without loop
if (head == NULL || head->next == NULL)
return NULL;
Node *slow = head, *fast = head;
// Move slow and fast 1 and 2 steps
// ahead respectively.
slow = slow->next;
fast = fast->next->next;
// Search for loop using slow and
// fast pointers
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
// If loop does not exist
if (slow != fast)
return NULL;
// If loop exists. Start slow from
// head and fast from meeting point.
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(50);
head->next = newNode(20);
head->next->next = newNode(15);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
Node* res = detectAndRemoveLoop(head);
if (res == NULL)
cout << "Loop does not exist";
else
cout << "Loop starting node is " << res->key;
return 0;
}
|
|
// Java program to return
// first node of loop.
import java.util.*;
class GFG{
static class Node
{
int key;
Node next;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
// A utility function to
// print a linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
// Function to detect and remove loop
// in a linked list that may contain loop
static Node detectAndRemoveLoop(Node head)
{
// If list is empty or has
// only one node without loop
if (head == null || head.next == null)
return null;
Node slow = head, fast = head;
// Move slow and fast 1
// and 2 steps ahead
// respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using
// slow and fast pointers
while (fast != null &&
fast.next != null)
{
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
// If loop does not exist
if (slow != fast)
return null;
// If loop exists. Start slow from
// head and fast from meeting point.
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
// Driver code
public static void main(String[] args)
{
Node head = newNode(50);
head.next = newNode(20);
head.next.next = newNode(15);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(10);
// Create a loop for testing
head.next.next.next.next.next = head.next.next;
Node res = detectAndRemoveLoop(head);
if (res == null)
System.out.print("Loop does not exist");
else
System.out.print("Loop starting node is " + res.key);
}
}
// This code is contributed by shikhasingrajput
|
|
# Python3 program to return first node of loop.
class Node:
def __init__(self, key):
self.key = key
self.next = None
def newNode(key):
temp = Node(key)
return temp
# A utility function to print a linked list
def printList(head):
while (head != None):
print(head.key, end = ' ')
head = head.next
print()
# Function to detect and remove loop
# in a linked list that may contain loop
def detectAndRemoveLoop(head):
# If list is empty or has only one node
# without loop
if (head == None or head.next == None):
return None
slow = head
fast = head
# Move slow and fast 1 and 2 steps
# ahead respectively.
slow = slow.next
fast = fast.next.next
# Search for loop using slow and
# fast pointers
while (fast and fast.next):
if (slow == fast):
break
slow = slow.next
fast = fast.next.next
# If loop does not exist
if (slow != fast):
return None
# If loop exists. Start slow from
# head and fast from meeting point.
slow = head
while (slow != fast):
slow = slow.next
fast = fast.next
return slow
# Driver code
if __name__=='__main__':
head = newNode(50)
head.next = newNode(20)
head.next.next = newNode(15)
head.next.next.next = newNode(4)
head.next.next.next.next = newNode(10)
# Create a loop for testing
head.next.next.next.next.next = head.next.next
res = detectAndRemoveLoop(head)
if (res == None):
print("Loop does not exist")
else:
print("Loop starting node is " +
str(res.key))
# This code is contributed by rutvik_56
|
|
// C# program to return
// first node of loop.
using System;
class GFG{
class Node
{
public int key;
public Node next;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
// A utility function to
// print a linked list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.key + " ");
head = head.next;
}
Console.WriteLine();
}
// Function to detect and remove loop
// in a linked list that may contain loop
static Node detectAndRemoveLoop(Node head)
{
// If list is empty or has
// only one node without loop
if (head == null || head.next == null)
return null;
Node slow = head, fast = head;
// Move slow and fast 1
// and 2 steps ahead
// respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using
// slow and fast pointers
while (fast != null &&
fast.next != null)
{
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
// If loop does not exist
if (slow != fast)
return null;
// If loop exists. Start slow from
// head and fast from meeting point.
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
// Driver code
public static void Main(String[] args)
{
Node head = newNode(50);
head.next = newNode(20);
head.next.next = newNode(15);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(10);
// Create a loop for testing
head.next.next.next.next.next =
head.next.next;
Node res = detectAndRemoveLoop(head);
if (res == null)
Console.Write("Loop does not exist");
else
Console.Write("Loop starting node is " +
res.key);
}
}
// This code is contributed by shikhasingrajput
|
|
<script>
// Javascript program to return
// first node of loop.
class Node
{
constructor(key)
{
this.key=key;
this.next=null;
}
}
// A utility function to
// print a linked list
function printList(head)
{
while (head != null)
{
document.write(head.key + " ");
head = head.next;
}
document.write("<br>");
}
// Function to detect and remove loop
// in a linked list that may contain loop
function detectAndRemoveLoop(head)
{
// If list is empty or has
// only one node without loop
if (head == null || head.next == null)
return null;
let slow = head, fast = head;
// Move slow and fast 1
// and 2 steps ahead
// respectively.
slow = slow.next;
fast = fast.next.next;
// Search for loop using
// slow and fast pointers
while (fast != null &&
fast.next != null)
{
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
// If loop does not exist
if (slow != fast)
return null;
// If loop exists. Start slow from
// head and fast from meeting point.
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
// Driver code
let head = new Node(50);
head.next = new Node(20);
head.next.next = new Node(15);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(10);
// Create a loop for testing
head.next.next.next.next.next = head.next.next;
let res = detectAndRemoveLoop(head);
if (res == null)
document.write("Loop does not exist");
else
document.write("Loop starting node is " + res.key);
// This code is contributed by unknown2108
</script>
|
Loop starting node is 15
How does this approach work?
Let slow and fast meet at some point after Floyd’s Cycle finding algorithm. The below diagram shows the situation when the cycle is found.
We can conclude below from the above diagram
Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer) (m + n*x + k) = 2*(m + n*y + k) Note that before meeting the point shown above, fast was moving at twice speed. x --> Number of complete cyclic rounds made by fast pointer before they meet first time y --> Number of complete cyclic rounds made by slow pointer before they meet first timeFrom the above equation, we can conclude below
m + k = (x-2y)*n Which means m+k is a multiple of n.So if we start moving both pointers again at the same speed such that one pointer (say slow) begins from the head node of the linked list and other pointers (say fast) begins from the meeting point. When the slow pointer reaches the beginning of the loop (has made m steps), the fast pointer would have made also moved m steps as they are now moving the same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning. Can they meet before also? No, because the slow pointer enters the cycle first time after m steps.
Method 2:
In this method, a temporary node is created. The next pointer of each node that is traversed is made to point to this temporary node. This way we are using the next pointer of a node as a flag to indicate whether the node has been traversed or not. Every node is checked to see if the next is pointing to a temporary node or not. In the case of the first node of the loop, the second time we traverse it this condition will be true, hence we return that node.
The code runs in O(n) time complexity and uses constant memory space.
Below is the implementation of the above approach:
|
// C++ program to return first node of loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
// Function to detect first node of loop
// in a linked list that may contain loop
Node* detectLoop(Node* head)
{
// Create a temporary node
Node* temp = new Node;
while (head != NULL) {
// This condition is for the case
// when there is no loop
if (head->next == NULL) {
return NULL;
}
// Check if next is already
// pointing to temp
if (head->next == temp) {
break;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node* nex = head->next;
// Make next point to temp
head->next = temp;
// Get to the next node in the list
head = nex;
}
return head;
}
/* Driver program to test above function*/
int main()
{
Node* head = newNode(50);
head->next = newNode(20);
head->next->next = newNode(15);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
Node* res = detectLoop(head);
if (res == NULL)
cout << "Loop does not exist";
else
cout << "Loop starting node is " << res->key;
return 0;
}
|
|
// Java program to return first node of loop
import java.util.*;
class GFG{
static class Node
{
int key;
Node next;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
// Function to detect first node of loop
// in a linked list that may contain loop
static Node detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
while (head != null)
{
// This condition is for the case
// when there is no loop
if (head.next == null)
{
return null;
}
// Check if next is already
// pointing to temp
if (head.next == temp)
{
break;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node nex = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return head;
}
/* Driver program to test above function*/
public static void main(String[] args)
{
Node head = newNode(50);
head.next = newNode(20);
head.next.next = newNode(15);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(10);
/* Create a loop for testing */
head.next.next.next.next.next = head.next.next;
Node res = detectLoop(head);
if (res == null)
System.out.print("Loop does not exist");
else
System.out.print("Loop starting node is " +
res.key);
}
}
// This code is contributed by gauravrajput1
|
|
# Python3 program to return first node of loop
class Node:
def __init__(self, x):
self.key = x
self.next = None
# A utility function to print a linked list
def printList(head):
while (head != None):
print(head.key, end = " ")
head = head.next
# Function to detect first node of loop
# in a linked list that may contain loop
def detectLoop(head):
# Create a temporary node
temp = Node(-1)
while (head != None):
# This condition is for the case
# when there is no loop
if (head.next == None):
return None
# Check if next is already
# pointing to temp
if (head.next == temp):
break
# Store the pointer to the next node
# in order to get to it in the next step
nex = head.next
# Make next point to temp
head.next = temp
# Get to the next node in the list
head = nex
return head
# Driver code
if __name__ == '__main__':
head = Node(50)
head.next = Node(20)
head.next.next = Node(15)
head.next.next.next = Node(4)
head.next.next.next.next = Node(10)
# Create a loop for testing
head.next.next.next.next.next = head.next.next
res = detectLoop(head)
if (res == None):
print("Loop does not exist")
else:
print("Loop starting node is ", res.key)
# This code is contributed by mohit kumar 29
|
|
// C# program to return first node of loop
using System;
class GFG{
class Node
{
public int key;
public Node next;
};
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.key + " ");
head = head.next;
}
Console.WriteLine();
}
// Function to detect first node of loop
// in a linked list that may contain loop
static Node detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
while (head != null)
{
// This condition is for the case
// when there is no loop
if (head.next == null)
{
return null;
}
// Check if next is already
// pointing to temp
if (head.next == temp)
{
break;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node nex = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return head;
}
// Driver code
public static void Main(String[] args)
{
Node head = newNode(50);
head.next = newNode(20);
head.next.next = newNode(15);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(10);
// Create a loop for testing
head.next.next.next.next.next = head.next.next;
Node res = detectLoop(head);
if (res == null)
Console.Write("Loop does not exist");
else
Console.Write("Loop starting node is " +
res.key);
}
}
// This code is contributed by Amit Katiyar
|
|
<script>
// javascript program to return first node of loop
class Node {
constructor() {
this.key = 0;
this.next = null;
}
}
function newNode(key) {
temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
// A utility function to print a linked list
function printList( head) {
while (head != null) {
document.write(head.key + " ");
head = head.next;
}
document.write("<br/>");
}
// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop( head) {
// Create a temporary node
temp = new Node();
while (head != null) {
// This condition is for the case
// when there is no loop
if (head.next == null) {
return null;
}
// Check if next is already
// pointing to temp
if (head.next == temp) {
break;
}
// Store the pointer to the next node
// in order to get to it in the next step
nex = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return head;
}
/* Driver program to test above function */
head = newNode(50);
head.next = newNode(20);
head.next.next = newNode(15);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(10);
/* Create a loop for testing */
head.next.next.next.next.next = head.next.next;
res = detectLoop(head);
if (res == null)
document.write("Loop does not exist");
else
document.write("Loop starting node is " + res.key);
// This code contributed by gauravrajput1
</script>
|
Method 3:
We can also use the concept of hashing in order to detect the first node of the loop. The idea is simple just iterate over the entire linked list and store node addresses in a set(C++ STL) one by one, while adding the node address into the set check if it already contains that particular node address if not then add node address to set if it is already present in the set then the current node is the first node of the loop.
|
// The below function take head of Linked List as
// input and return Address of first node in
// the loop if present else return NULL.
/* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };*/
ListNode* detectCycle(ListNode* A)
{
// declaring map to store node address
unordered_set<ListNode*> uset;
ListNode *ptr = A;
// Default consider that no cycle is present
while (ptr != NULL) {
// checking if address is already present in map
if (uset.find(ptr) != uset.end())
return ptr;
// if address not present then insert into the set
else
uset.insert(ptr);
ptr = ptr->next;
}
return NULL;
}
// This code is contributed by Pankaj_Joshi
|
|
// The below function take head of Linked List as
// input and return Address of first node in
// the loop if present else return NULL.
import java.io.*;
import java.util.*;
class GFG
{
static Node detectCycle(Node A)
{
// declaring map to store node address
Set<Node> uset = new HashSet<Node>();
Node = A;
// Default consider that no cycle is present
while (ptr != NULL)
{
// checking if address is already present in map
if(uset.contains(ptr))
{
return ptr;
}
// if address not present then insert into the set
else
{
uset.add(ptr);
}
ptr = ptr.next;
}
return null;
}
}
// This code is contributed by avanitrachhadiya2155
|
|
# The below function take head of Linked List as
# input and return Address of first node in
# the loop if present else return NULL.
''' Definition for singly-linked list.
* class ListNode:
* def __init__(self, x):
* self.val=x
* self.next=None
* '''
def detectCycle(A):
# Declaring map to store node
# address
uset = set()
ptr = A
# Default consider that no cycle
# is present
while (ptr != None):
# Checking if address is already
# present in map
if (ptr in uset):
return ptr
# If address not present then
# insert into the set
else:
uset.add(ptr)
ptr = ptr.next
return None
# This code is contributed by pratham76
|
|
// The below function take head of Linked List as
// input and return Address of first node in
// the loop if present else return NULL.
using System.Collections.Generic;
public class GFG
{
class Node
{
public int key;
public Node next;
};
static Node detectCycle(Node A)
{
// declaring map to store node address
HashSet<Node> uset = new HashSet<Node>();
Node ptr = A;
// Default consider that no cycle is present
while (ptr != null)
{
// checking if address is already present in map
if(uset.Contains(ptr))
{
return ptr;
}
// if address not present then insert into the set
else
{
uset.Add(ptr);
}
ptr = ptr.next;
}
return null;
}
}
// This code is contributed by 29AjayKumar
|
|
<script>
// The below function take head of Linked List as
// input and return Address of first node in
// the loop if present else return NULL.
function detectCycle(A)
{
// declaring map to store node address
let uset = new Set();
let ptr = A;
// Default consider that no cycle is present
while (ptr != NULL)
{
// checking if address is already present in map
if(uset.has(ptr))
{
return ptr;
}
// if address not present then insert into the set
else
{
uset.add(ptr);
}
ptr = ptr.next;
}
return null;
}
// This code is contributed by patel2127
</script>
|