Detect Loop in linked list Python

PROGRAM TO DETECT AND REMOVE LOOP IN A LINKED LIST



class LinkedList {
 
    static Node head;
 
    static class Node {
 
        int data;
        Node next;
 
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function that detects loop in the list
    void detectAndRemoveLoop(Node node)
    {
 
        // If list is empty or has only one node
        // without loop
        if (node == null || node.next == null)
            return;
 
        Node slow = node, fast = node;
 
        // 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 exists */
        if (slow == fast) {
            slow = node;
            while (slow.next != fast.next) {
                slow = slow.next;
                fast = fast.next;
            }
 
            /* since fast->next is the looping point */
            fast.next = null; /* remove loop */
        }
    }
 
    // Function to print the linked list
    void printList(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(50);
        list.head.next = new Node(20);
        list.head.next.next = new Node(15);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(10);
 
        // Creating a loop for testing
        head.next.next.next.next.next = head.next.next;
        list.detectAndRemoveLoop(head);
        System.out.println("Linked List after removing loop : ");
        list.printList(head);
    }
}class Node:
 
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    def detectAndRemoveLoop(self):
 
        if self.head is None:
            return
        if self.head.next is None:
            return
 
        slow = self.head
        fast = self.head
 
        # Move slow and fast 1 and 2 steps respectively
        slow = slow.next
        fast = fast.next.next
 
        # Search for loop using slow and fast pointers
        while (fast is not None):
            if fast.next is None:
                break
            if slow == fast:
                break
            slow = slow.next
            fast = fast.next.next
 
        # if loop exists
        if slow == fast:
            slow = self.head
            while (slow.next != fast.next):
                slow = slow.next
                fast = fast.next
 
            # Sinc fast.next is the looping point
            fast.next = None  # Remove loop
 
    # Utility function to print the linked LinkedList
 
    def printList(self):
        temp = self.head
        while(temp):
            print temp.data,
            temp = temp.next
 
 
# Driver program
llist = LinkedList()
llist.head = Node(50)
llist.head.next = Node(20)
llist.head.next.next = Node(15)
llist.head.next.next.next = Node(4)
llist.head.next.next.next.next = Node(10)
 
# Create a loop for testing
llist.head.next.next.next.next.next = llist.head.next.next
 
llist.detectAndRemoveLoop()
 
print "Linked List after removing loop"
llist.printList()


OUTPUT
Linked List after removing loop 
50 20 15 4 10

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more