Skip to main content

Finding a loop in a linked List

Finding a loop in a linked List:-

public class LinkedListLoop {

 //Two pointers
 public Node loopCheck(Node head)
 {
  //fast pointer take two steps at a time
  Node fastptr=head;
  //slow pointer take one step at a time
  Node slowptr=head;
  
  if(head==null)
  {
   System.out.println("no loops empty list");
  }
  
  //Till any pointer becomes null
  while(slowptr!=null && fastptr!=null && fastptr.next!=null)
  {
   slowptr=slowptr.next;
   fastptr=fastptr.next.next;
   
   //if both pointers point to same node
   //possible only in loop list
   if(slowptr==fastptr)
   {
    System.out.println("loopfound");
    fastptr=head;
    while(fastptr.next!=slowptr)
    {
     fastptr=fastptr.next;
    }
     return fastptr;
   }
  }
  System.out.println("loop not found");
   return head;
 }
 
 public void makeCycle(Node head)
 {
  Node temp=head;
  while(temp.next.next!=null)
  {
   temp=temp.next;
  }
  temp.next=head.next.next;
 }
 
 
}

Comments

.

Popular posts from this blog

Best LeetCode Lists for Interviews

Here is a list of some of the best questions asked in interviews:-  Must do 75 https://leetcode.com/list/5hkn6wze/ Must do 60  https://leetcode.com/list/5eie1aqd/ Must do medium:-  https://leetcode.com/list/5xaelz7g/ Must do Easy:-   https://leetcode.com/list/5r7rxpr1/ Graph:-  https://leetcode.com/list/x18ervrd/  Dynamic Programming:-    https://leetcode.com/list/x14z0dxr/  FaceBook interviews:- https://leetcode.com/list/xyu98pv6/  Amazon Interviews:-  https://leetcode.com/list/5hkniyf7/  Google Interviews:- https://leetcode.com/list/xyu9xfo1/ https://github.com/nazarmubeen/TopProblems/blob/master/README.md

DECODE WAYS - LEETCODE PROBLEM 91

  A message containing letters from   A-Z   is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a  non-empty  string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation:  It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation:  It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). class Solution { public int numDecodings(String s) { int ways=0; ways=countDecoding(s.toCharArray(),s.length()); return ways; } int countDecoding(char[] digits, int n){ // System.out.println(" digits "+disgits[0]); // for base condition "01123" should return 0 // base cases if (n == 0 || (n == 1 && digits[0]!='...