Chapter 22:LinkedList(Part 2)

LinkedList (Part 2): Advanced Concepts in Linked Lists

In the previous part of our LinkedList series, we covered the fundamentals, including how to create a Node class, and implement methods like addFirst(), addLast(), and removeFirst(). Now, in this chapter, we will dive deeper into more complex concepts and operations on LinkedLists. This will strengthen our understanding of both LinkedList theory and its applications in Data Structures and Algorithms (DSA). The topics we will cover include detecting and removing cycles, sorting linked lists using merge sort, implementing a zigzag pattern, exploring doubly and circular linked lists, and more.

Topics Covered:

Detecting a cycle in a linked list
Code: Detecting a cycle in a linked list
Removing a cycle from a linked list
Code: Removing a cycle from a linked list
Explanation: Cycle removal and its mathematical proof
Linked List in Java Collection Framework (JCF)
Merge sort on a linked list
Code: Merge sort on a linked list
Zigzag linked list reordering
Code: Zigzag linked list
Doubly linked list
Circular linked list
Practice problems

1. Detecting a Cycle in a Linked List

A linked list can have cycles, where a node points back to a previous node in the list, forming a loop. To detect a cycle in a linked list, we use the Floyd’s Cycle Detection Algorithm (also called the Tortoise and Hare algorithm). In this approach, we have two pointers:

A slow pointer that moves one step at a time.
A fast pointer that moves two steps at a time.

If the fast pointer ever meets the slow pointer, then a cycle exists.

2. Detecting a Cycle in a Linked List Code

Here’s the Java implementation of cycle detection in a linked list:

class ListNode {
    int data;
    ListNode next;

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

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {
                return true; // Cycle detected
            }
        }
        return false; // No cycle detected
    }
}

3. Removing a Cycle in a Linked List

After detecting a cycle, the next task is to remove it. To remove a cycle, we need to find the starting point of the loop. Once found, we can set the next pointer of the last node in the loop to null.

4. Removing a Cycle in a Linked List Code

Here’s the code for removing a cycle from a linked list:

public class LinkedListCycle {
    // Detect and remove cycle
    public void removeCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // Detect cycle
        do {
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        // Find start of cycle
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove cycle by setting the last node's next to null
        ListNode prev = fast;
        while (prev.next != fast) {
            prev = prev.next;
        }
        prev.next = null;
    }
}

5. Explanation: Cycle Removal and Its Mathematical Proof

The approach of detecting and removing cycles is based on the fact that when the two pointers meet inside the cycle, the distance traveled by the fast pointer is twice that of the slow pointer. By resetting one pointer to the head and moving both pointers one step at a time, they meet at the start of the cycle. We use this mathematical property to find and remove the cycle.

6. Java Collection Framework (JCF) and Linked Lists

Java provides a built-in implementation of Linked Lists as part of its Java Collection Framework (JCF). The LinkedList class in the java.util package implements the List, Deque, and Queue interfaces, making it versatile. It supports operations like adding/removing elements at both ends, which makes it suitable for many algorithms.

7. Linked List in Java Collection Framework

Here’s a basic usage of LinkedList in Java:

import java.util.LinkedList;

public class JCFLinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.addFirst(10);
        list.addLast(20);
        list.add(15);  // Add at the end

        System.out.println("LinkedList: " + list);

        list.removeFirst();
        System.out.println("After removing first: " + list);
    }
}

8. Merge Sort on a Linked List

Merge sort is an efficient, stable, and comparison-based sorting algorithm that can be applied to linked lists. Since linked lists do not allow random access, algorithms like merge sort, which work by splitting the list into halves, are more efficient.

9. Merge Sort on a Linked List Code

Here’s how merge sort can be implemented on a linked list:

public class LinkedListMergeSort {

    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode middle = getMiddle(head);
        ListNode nextOfMiddle = middle.next;
        middle.next = null;

        ListNode left = mergeSort(head);
        ListNode right = mergeSort(nextOfMiddle);

        return merge(left, right);
    }

    private ListNode getMiddle(ListNode head) {
        if (head == null) return head;

        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        if (left == null) return right;
        if (right == null) return left;

        if (left.data <= right.data) {
            left.next = merge(left.next, right);
            return left;
        } else {
            right.next = merge(left, right.next);
            return right;
        }
    }
}

10. Zigzag Linked List Reordering

Zigzag reordering of a linked list involves rearranging the list such that elements follow a zigzag pattern (greater-smaller-greater).

11. Zigzag Linked List Code

Here’s the code for zigzag reordering:

public class ZigzagLinkedList {

    public void zigzagReorder(ListNode head) {
        boolean flag = true; // We expect smaller, then larger, and so on.
        ListNode curr = head;

        while (curr != null && curr.next != null) {
            if (flag) {
                // If the current node's data is greater than next, swap them
                if (curr.data > curr.next.data) {
                    int temp = curr.data;
                    curr.data = curr.next.data;
                    curr.next.data = temp;
                }
            } else {
                // If the current node's data is smaller than next, swap them
                if (curr.data < curr.next.data) {
                    int temp = curr.data;
                    curr.data = curr.next.data;
                    curr.next.data = temp;
                }
            }
            flag = !flag; // Toggle between smaller and greater expectations
            curr = curr.next;
        }
    }
}

12. Doubly Linked List

A doubly linked list is a variation of a linked list where each node points to both its previous and next nodes. This allows traversal in both directions.

13. Circular Linked List

A circular linked list is a type of linked list where the last node points back to the head, forming a circle. This is useful in applications like task scheduling or round-robin algorithms.

14. Practice Questions

Detect and remove cycle in a linked list.
Implement merge sort on a linked list.
Reorder a linked list in zigzag fashion.
Convert a singly linked list into a doubly linked list.

This concludes the second chapter on Linked Lists, where we explored advanced topics like cycle detection, removal, merge sort, and more. Continue practicing with the problems provided to strengthen your understanding of linked lists!

Related Posts in My Series:

DSA in Java Series:

Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.
Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.
Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

LinkedIn: Connect with me for professional updates and insights.
GitHub: Explore my repositories and contributions to various projects.
LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast