Floyd’s Cycle Finding Algorithm

1. Detect the Starting Node of the Loop in a Linked List

class LinkedList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    // Function to detect the starting node of the cycle
    public Node findCycleStart() {
        Node slow = head;
        Node fast = head;

        // Step 1: Detect if there is a cycle using Floyd’s Cycle Detection Algorithm
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {  // Cycle detected
                // Step 2: Reset slow pointer to head
                slow = head;

                // Step 3: Move both slow and fast one step at a time
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }

                return slow;  // This is the starting node of the loop
            }
        }

        return null;  // No cycle found
    }

    // Function to add a new node at the end of the list
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }

    // Function to create a loop (for testing)
    public void createLoop(int position) {
        if (head == null) return;

        Node temp = head;
        Node loopNode = null;
        int count = 1;

        while (temp.next != null) {
            if (count == position) {
                loopNode = temp;
            }
            temp = temp.next;
            count++;
        }

        if (loopNode != null) {
            temp.next = loopNode;
        }
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);
        list.append(5);
        list.append(6);

        list.createLoop(3); // Creating a loop at node with value 3

        Node loopStart = list.findCycleStart();
        if (loopStart != null) {
            System.out.println("Cycle starts at node with value: " + loopStart.data);
        } else {
            System.out.println("No cycle detected.");
        }
    }
}

 

 

2. Check If a Linked List is a Palindrome

 

class LinkedList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    // Function to check if the linked list is a palindrome
    public boolean isPalindrome() {
        if (head == null || head.next == null) return true; // Edge case: empty or single node

        // Step 1: Find the middle of the list
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;      
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the list
        Node secondHalf = reverseList(slow);

        // Step 3: Compare both halves
        Node firstHalf = head;
        Node temp = secondHalf;
        boolean isPalindrome = true;

        while (temp != null) {  // Compare until the end of the second half
            if (firstHalf.data != temp.data) {
                isPalindrome = false;
                break;
            }
            firstHalf = firstHalf.next;
            temp = temp.next;
        }

        // Step 4: Restore the list (Optional, if we need the original order)
        reverseList(secondHalf);

        return isPalindrome;
    }

    // Function to reverse a linked list
    private Node reverseList(Node head) {
        Node prev = null;
        Node current = head;

        while (current != null) {
            Node nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }

    // Function to add a new node at the end of the list
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(2);
        list.append(1);

        System.out.println("Is Palindrome? " + list.isPalindrome()); // Output: true

        LinkedList list2 = new LinkedList();
        list2.append(1);
        list2.append(2);
        list2.append(3);
        list2.append(4);
        list2.append(5);

        System.out.println("Is Palindrome? " + list2.isPalindrome()); // Output: false
    }
}