Removing a loop in a singly linked list

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Problem: Remove a loop from a singly linked list if the list has a loop. Example For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4. Solution The problem has 3 steps : Detect if there is a loop in the list (already solved here) Identify the start of the loop (already discussed here) Delete the loop, which we will discuss here. [Read More]
kodeknight  Single Link List  loop 

Y – shaped Linked List. Algorithm to find the node of intersection of two lists.

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Find the node of intersection of 2 lists. Example: Solution Method 1 - Taking advantage of the link list length Here is the pseudo code to find the node of intersection of 2 lists: 1) Go through L1 and get its length l1 2) Go through L2 and get its length l2 3) Now find the difference d = l1-l2 4) So d is the number of nodes that are extra in longer list. [Read More]
kodeknight  link list  Single Link List  loop  intersection 

Finding the Start of a Loop in a Linked List

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  9 minutes  |  Kinshuk Chandra

Problem  Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C Example head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ | | | +------------------------+ Answer here is 3. [Read More]
kodeknight  link list  java-code  Single Link List  loop  CrackingTheCodingInterview 

Detecting a loop in a linked list

 Posted on April 8, 2010  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem : Given a singly linked list, find if there exist a loop. Example A -> B -> C -> D -> E -> C [ E again point to C] Solutions Method 1 - Using hashing 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. [Read More]
kodeknight  link list  Single Link List  loop  fast pointer