Copy List with Random Pointer

This problem is a classic deep copy scenario, similar to graph cloning (e.g., LeetCode 133).

Approach:

1. Traverse the list once to copy the next pointers.
2. During this traversal, store the mapping between original nodes and their copies in a hash map.
3. Traverse the list a second time to copy the random pointers by using the map to find the corresponding copied node.

Reverse Linked List II

Manipulating linked lists often requires careful pointer management. A good strategy is to first sketch the operations on paper before coding.

Technique: Use a dummy node to simplify edge cases, such as when the reversal starts from the head of the list.

Approach:

1. Use three pointers: current, temp, and previous for in-place reversal.
2. Reassign pointers to reverse the sublist:
   1. current.next points to temp.next.
   2. temp.next points to current.
   3. previous.next points to temp.
3. After reversing the specified section, reconnect it to the original list by setting the previous node's next to the new head of the reversed sublist and the tail of the reversed sublist's next to the node after the original sublist.

Linked List Cycle

Approach: Implement the solution using the fast and slow pointer technique.

Edge Cases to Consider:

• head is null.
• The list has only one node.
• The list has exactly two nodes.

public class LinkedListCycleDetector {
    public boolean hasCycle(ListNode head) {
        ListNode slowPtr = head;
        ListNode fastPtr = head;

        while (fastPtr != null && fastPtr.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr) {
                return true;
            }
        }

        return false;
    }
}

Reverse Linked List

Summary of List Operations:

1. Temporarily store a node (e.g., ListNode node = ...).
2. Modify a node's pointer (e.g., current.next = ...).
3. Move pointers forward (e.g., previous = current or store current).
4. Advance to the next node (e.g., current = next).

class ListReverser {
    public ListNode reverseList(ListNode head) {
        ListNode previousNode = null;
        ListNode currentNode = head;
        while (currentNode != null) {
            ListNode nextNode = currentNode.next; // Store the subsequent node
            currentNode.next = previousNode;     // Reverse the link
            previousNode = currentNode;          // Move the previous pointer forward
            currentNode = nextNode;              // Advance to the next node
        }

        return previousNode;
    }
}

Remove Nth Node From End of List

Three Approaches:

1. Calculate the list's size, then move a pointer to the node just before the target.
2. Use a stack to store nodes and then pop to find the target.
3. The most efficient method is the two-pointer technique: advance one pointer n nodes ahead, then move both pointers until the first one reaches the end. The second pointer will then be at the node preceding the one to be deleted.

Remove Duplicates from Sorted List II

Approach: Two Pointers

1. Traverse the list with two pointers, current and previous.
2. If the next node's value is a duplicate, advance the current pointer to skip all nodes with that value.
3. If not a duplicate, check if previous and current are adjacent. If they are, move previous forward. If not, it means a duplicate was just skipped, so set previous.next to the current node to remove the duplicates.
4. Always advance the current pointer.
5. Finally, ensure the last segment of the list is correctly terminated.

class DuplicateRemover {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode previous = dummy;
        ListNode current = head;

        while (current != null && current.next != null) {
            if (current.val == current.next.val) {
                int duplicateValue = current.val;
                while (current != null && current.val == duplicateValue) {
                    current = current.next;
                }
                previous.next = current;
            } else {
                previous = current;
                current = current.next;
            }
        }
        return dummy.next;
    }
}

Rotate List

Approach:

1. Find the length of the list.
2. Calculate the effective number of rotations by taking k % length.
3. Handle edge cases where k is 0, the list has one node, or k % length is 0.
4. Find the new tail (the node at position length - k - 1) and the new head (the node at position length - k).
5. Disconnect the list at the new tail and reconnect it so the new tail's next is null and the old tail's next points to the original head.

class ListRotator {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        // Find the length and the last node
        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        int rotations = k % length;
        if (rotations == 0) {
            return head;
        }

        // Find the new tail (node before new head)
        ListNode newTail = head;
        for (int i = 0; i < length - rotations - 1; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null; // Break the list
        tail.next = head;    // Connect the old tail to the old head

        return newHead;
    }
}

Partition List

Approach: Use two dummy nodes to build two separate lists: one for nodes with values less than x and another for nodes with values greater than or equal to x. Then, connect the two lists.

Improtant Bug Fix: When splitting a list, you must explicitly set the next pointer of the tail of the second list to null. Otherwise, the original links remain, creating a cycle when the lists are concatenated.

class ListPartitioner {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyLow = new ListNode(0);
        ListNode tailLow = dummyLow;
        ListNode dummyHigh = new ListNode(0);
        ListNode tailHigh = dummyHigh;

        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                tailLow.next = current;
                tailLow = tailLow.next;
            } else {
                tailHigh.next = current;
                tailHigh = tailHigh.next;
            }
            current = current.next;
        }

        tailHigh.next = null; // Crucial: Break the link to prevent a cycle
        tailLow.next = dummyHigh.next;
        return dummyLow.next;
    }
}

LRU Cache

Approach:

1. Use a hash map for O(1) time complexity for get and put operations.
2. Use a doubly linked list to mainatin the order of access, with the most recently used item at the head and the least recently used at the tail.

public class LRUCache {
    class CacheNode {
        int key;
        int value;
        CacheNode prev;
        CacheNode next;
        CacheNode() {}
        CacheNode(int _key, int _value) { key = _key; value = _value; }
    }

    private final Map<integer cachenode=""> nodeMap = new HashMap<>();
    private int capacity;
    private CacheNode dummyHead, dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // Initialize dummy head and tail
        dummyHead = new CacheNode();
        dummyTail = new CacheNode();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        CacheNode node = nodeMap.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        CacheNode node = nodeMap.get(key);
        if (node == null) {
            CacheNode newNode = new CacheNode(key, value);
            nodeMap.put(key, newNode);
            addToHead(newNode);
            if (nodeMap.size() > capacity) {
                CacheNode tail = removeTail();
                nodeMap.remove(tail.key);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(CacheNode node) {
        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    private void removeNode(CacheNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(CacheNode node) {
        removeNode(node);
        addToHead(node);
    }

    private CacheNode removeTail() {
        CacheNode tailNode = dummyTail.prev;
        removeNode(tailNode);
        return tailNode;
    }
}
</integer>