Linear data structures fall into two primary categories: contiguous arrays and linked sequences. A linked sequence organizes elements as self-contained units connected via references. Each unit, called a node, holds two parts: stored data and a reference pointing to the subsequent node, with the final unit referencing a null value to mark the end. To manage a linked sequence effectively, we track individual nodes (each with data and reference) and a size counter. The size counter simplifies validating insertion/deletion positions, which is a common oversight.

Remove All Target Nodes from a Linked List

Given the head of a singly linked sequence and an integer target, erase every node where the stored value equals target, then return the modified sequence's new head.

Example 1

Input: head = [1,2,6,3,4,5,6], target = 6
Output: [1,2,3,4,5]

Example 2

Input: head = [], target = 1
Output: []

Example 3

Input: head = [7,7,7,7], target = 7
Output: []

Implementation Notes

To delete all matching nodes, iterate through the sequence, checking each node's value. Deleting a node requires updating its predecessor's reference to skip it, so maintaining a trailing reference is critical. Without a dummy head, handling a head node that matches target requires separate logic. Adding a dummy head creates a consistent predecessor for every node, including the original first one, unifying deletion operations.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int target) {
        ListNode dummy = new ListNode(-1, head);
        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.val == target) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return dummy.next;
    }
}

Implement a Custom Singly Linked List

Build either a singly or doubly linked sequence. For a singly linked one, nodes have val (stored data) and next (reference to the next node). For doubly linked, add prev (reference to the prior node). Assume all nodes use 0-based indexing.

Implement the CustomLinkedList class:

• CustomLinkedList() Initialize an empty linked sequence.
• int get(int idx) Retrieve the value at 0-based index idx. Return -1 if invalid.
• void prepend(int val) Insert a node with val before the first element. The new node becomes the first node.
• void append(int val) Insert a node with val after the last element.
• void insertAt(int idx, int val) Insert a node with val before the node at 0-based index idx. If idx equals the sequence length, append it. If idx exceeds the length, skip insertion.
• void deleteAt(int idx) Remove the node at 0-based index idx if valid.

Example

Input
["CustomLinkedList", "prepend", "append", "insertAt", "get", "deleteAt", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Implementation Notes

Using a dummy head simplifies prepend and delete operations at the 0 index, as all insertions and deletions can use the same predecessor-finding logic. The size counter ensures quick validity checks and efficient append operations by avoiding full traversal.

class CustomListNode {
    int value;
    CustomListNode next;
    CustomListNode() {}
    CustomListNode(int value) { this.value = value; }
}

class CustomLinkedList {
    private int nodeCount;
    private CustomListNode dummyHead;

    public CustomLinkedList() {
        nodeCount = 0;
        dummyHead = new CustomListNode();
    }
    
    public int get(int idx) {
        if (idx < 0 || idx >= nodeCount) {
            return -1;
        }
        CustomListNode temp = dummyHead;
        for (int i = 0; i <= idx; i++) {
            temp = temp.next;
        }
        return temp.value;
    }
    
    public void prepend(int value) {
        insertAt(0, value);
    }
    
    public void append(int value) {
        insertAt(nodeCount, value);
    }
    
    public void insertAt(int idx, int value) {
        if (idx > nodeCount) {
            return;
        }
        idx = Math.max(0, idx);
        CustomListNode predecessor = dummyHead;
        for (int i = 0; i < idx; i++) {
            predecessor = predecessor.next;
        }
        CustomListNode newNode = new CustomListNode(value);
        newNode.next = predecessor.next;
        predecessor.next = newNode;
        nodeCount++;
    }
    
    public void deleteAt(int idx) {
        if (idx < 0 || idx >= nodeCount) {
            return;
        }
        CustomListNode predecessor = dummyHead;
        for (int i = 0; i < idx; i++) {
            predecessor = predecessor.next;
        }
        predecessor.next = predecessor.next.next;
        nodeCount--;
    }
}

/**
 * Your CustomLinkedList object will be instantiated and called as such:
 * CustomLinkedList obj = new CustomLinkedList();
 * int param_1 = obj.get(idx);
 * obj.prepend(value);
 * obj.append(value);
 * obj.insertAt(idx,value);
 * obj.deleteAt(idx);
 */

Reverse a Singly Linked List

Given the head of a singly linked sequence, reverse it in-place and return the new head of the reversed sequence.

Example

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Implementation Notes

A common approach uses three pointers to reverse links incrementally without extra space. One pointer tracks the reversed segment's tail (initially null), another the current node being processed, and a third to save the next node before oevrwriting its reference. After processing all nodes, the reversed segment's tail becomes the new head.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode reversedTail = null;
        ListNode currentNode = head;
        while (currentNode != null) {
            ListNode nextOriginal = currentNode.next;
            currentNode.next = reversedTail;
            reversedTail = currentNode;
            currentNode = nextOriginal;
        }
        return reversedTail;
    }
}