Loop in a Singly Linked List

Overview : 

A Linked List is considered to have a loop or a cycle , if a node is visited more than once while traversing the list.

Problem :

Given a singly linked list , detect wether it has a loop or not . Note that the head pointer may be 'null' if the list is empty.
( Problem Source : Cracking the coding interview : HackerRank)



Solution :

The solution is based on floyd's cycle finding algorithm , also referred to as the 'Tortoise and Hare' algorithm. It uses two pointers , which move at different speeds.  Let us call them as slow and fast pointers.  Now the fast pointer can move at any speed which should be greater than slow pointer's speed. Simple mathematics* suggests that if we move the fast pointer with speed twice that of slow , and if they meet , the linked list has a cycle .

*Why fast = slow * 2 ?

Below is the java code for the logic .

Reverse a singly linked list : Recursively

Following approach can be followed to reverse a singly linked list recursively



Approach : 

1.Divide the list in two parts : first and rest.
2.Recursively call the reverse method with rest.
3.link rest-->first
4.fix the last node

Implementation: 


public node reverse(Node head){

if( head==null) return;

Node first= head;
Node rest= first.next;

if(rest== null) return;

reverse(rest); //recursively call reverse for the rest .

first.next.next= first;// next now points to current

first.next = null; //fix the last node

head= rest;

return head;

}

Complexity :

Time: O(n)
Space: O(1)

Reverse a Single linked list : Iterative method

Following is a simple iterative Method for reversing a singly linked list


public node reverse(Node head){


if(head==null) return;

Node current= head;
Node prev= null;
Node next= null;


while(current!=null){

next= current.next;

current.next= prev;

prev= current;

current= next;
}


head= prev;

return head;

}