Linked List Implementation

Singly Linked List (25 points)

Create a class SinglyLinkedList.java with a nested Node class:

public class SinglyLinkedList<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node head;
    private Node tail;
    private int size;
    
    // Required methods (implement all):
    public void addFirst(T data);      // O(1)
    public void addLast(T data);       // O(1) with tail pointer
    public void addAt(int index, T data); // O(n)
    
    public T removeFirst();            // O(1)
    public T removeLast();             // O(n) - must traverse
    public T removeAt(int index);      // O(n)
    public boolean remove(T data);     // Remove first occurrence
    
    public T getFirst();               // O(1)
    public T getLast();                // O(1) with tail pointer
    public T get(int index);           // O(n)
    public int indexOf(T data);        // O(n)
    public boolean contains(T data);   // O(n)
    
    public int size();
    public boolean isEmpty();
    public void clear();
    public void printList();           // Print all elements
}

Requirements:

• Use generics (<T>) for type safety
• Maintain both head and tail pointers
• Track size for O(1) size() operation
• Throw appropriate exceptions for invalid operations

Doubly Linked List (25 points)

Create a class DoublyLinkedList.java with bidirectional navigation:

public class DoublyLinkedList<T> {
    private class Node {
        T data;
        Node prev;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node head;
    private Node tail;
    private int size;
    
    // All methods from SinglyLinkedList, PLUS:
    public T removeLast();             // O(1) - with prev pointer!
    public void reverse();             // O(n) - in-place reversal
    public void printReverse();        // Print from tail to head
    
    // Iterator-like methods:
    public Node getHead();             // For external traversal
    public Node getTail();
}

Key Improvement: removeLast() should be O(1) using the prev pointer!

Circular Linked List (25 points)

Create a class CircularLinkedList.java where the last node points back to head:

public class CircularLinkedList<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node head;
    private Node tail;  // tail.next always points to head
    private int size;
    
    // Core operations:
    public void add(T data);           // Add at end
    public void addFirst(T data);      // Add at beginning
    public T remove(T data);           // Remove first occurrence
    public T removeFirst();
    
    // Circular-specific operations:
    public void rotate(int k);         // Rotate list by k positions
    public boolean isCircular();       // Verify circular property
    public void traverse(int times);   // Print list 'times' rotations
    
    // Josephus Problem:
    public T josephus(int k);          // Return survivor (every k-th eliminated)
}

// Josephus Problem Example:
// People in circle: [1, 2, 3, 4, 5], eliminate every 2nd person
// Elimination order: 2, 4, 1, 5
// Survivor: 3
CircularLinkedList<Integer> circle = new CircularLinkedList<>();
for (int i = 1; i <= 5; i++) circle.add(i);
circle.josephus(2);  // Returns: 3

Cycle Detection & Analysis (15 points)

Implement cycle detection using Floyd's algorithm:

public class LinkedListProblems {
    
    // P4a: Detect if a cycle exists
    public boolean hasCycle(ListNode head);
    
    // P4b: Find the node where cycle begins (return null if no cycle)
    public ListNode detectCycleStart(ListNode head);
    
    // P4c: Find the length of the cycle (return 0 if no cycle)
    public int cycleLength(ListNode head);
}

// Example:
// 1 -> 2 -> 3 -> 4 -> 5
//           ^         |
//           |_________|
// hasCycle() returns true
// detectCycleStart() returns node with value 3
// cycleLength() returns 3

Reversal Operations (15 points)

Implement various reversal techniques:

// P5a: Reverse entire list iteratively
public ListNode reverseIterative(ListNode head);

// P5b: Reverse entire list recursively
public ListNode reverseRecursive(ListNode head);

// P5c: Reverse nodes in groups of k
// [1,2,3,4,5], k=2 → [2,1,4,3,5]
// [1,2,3,4,5], k=3 → [3,2,1,4,5]
public ListNode reverseInGroups(ListNode head, int k);

// P5d: Reverse between positions left and right (1-indexed)
// [1,2,3,4,5], left=2, right=4 → [1,4,3,2,5]
public ListNode reverseBetween(ListNode head, int left, int right);

Fast & Slow Pointer Problems (15 points)

Use the two-pointer technique:

// P6a: Find the middle node (if even length, return second middle)
// [1,2,3,4,5] → 3
// [1,2,3,4] → 3
public ListNode findMiddle(ListNode head);

// P6b: Check if list is palindrome
// [1,2,3,2,1] → true
// [1,2,3,4] → false
public boolean isPalindrome(ListNode head);

// P6c: Find nth node from end
// [1,2,3,4,5], n=2 → 4
public ListNode nthFromEnd(ListNode head, int n);

// P6d: Remove nth node from end and return head
// [1,2,3,4,5], n=2 → [1,2,3,5]
public ListNode removeNthFromEnd(ListNode head, int n);

Merge & Sort Operations (15 points)

Implement merging and sorting for linked lists:

// P7a: Merge two sorted lists into one sorted list
// [1,3,5] + [2,4,6] → [1,2,3,4,5,6]
public ListNode mergeTwoSorted(ListNode l1, ListNode l2);

// P7b: Merge k sorted lists
// [[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6]
public ListNode mergeKSorted(ListNode[] lists);

// P7c: Sort a linked list using merge sort - O(n log n)
public ListNode sortList(ListNode head);

// P7d: Partition list around value x
// All nodes less than x come before nodes >= x
// [1,4,3,2,5,2], x=3 → [1,2,2,4,3,5]
public ListNode partition(ListNode head, int x);

Advanced Linked List Problems (15 points)

Solve these challenging problems:

// P8a: Find intersection point of two lists
// List1: 1 -> 2 -> 3
//                   \
//                    -> 6 -> 7 -> null
//                   /
// List2:      4 -> 5
// Returns: node with value 6
public ListNode getIntersection(ListNode headA, ListNode headB);

// P8b: Add two numbers represented as linked lists (digits reversed)
// [2,4,3] + [5,6,4] = 342 + 465 = 807 → [7,0,8]
public ListNode addTwoNumbers(ListNode l1, ListNode l2);

// P8c: Flatten a multilevel doubly linked list
// 1 - 2 - 3 - 4 - 5
//     |
//     6 - 7
//     |
//     8
// Flattens to: 1 - 2 - 6 - 8 - 7 - 3 - 4 - 5
public DoublyListNode flatten(DoublyListNode head);

// P8d: Copy list with random pointer
// Each node has a random pointer to any node or null
public RandomListNode copyRandomList(RandomListNode head);