203. Remove Linked List Elements

Given the head of a linked list and an integer val, remove all nodes with value equal to val and return the new head.

public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    if (head == null) return null;

    ListNode prev = head;
    ListNode current = head.next;

    while (current != null) {
        if (current.val == val) {
            prev.next = current.next;
        } else {
            prev = current;
        }
        current = current.next;
    }
    return head;
}

707. Design Linked List

Design a singly linked list that supports operations for getting, adding at head, adding at tail, adding at index, and deleting at index.

class SinglyLinkedList {
    private int count;
    private ListNode dummyHead;

    public SinglyLinkedList() {
        count = 0;
        dummyHead = new ListNode(0);
    }

    public int get(int idx) {
        if (idx < 0 || idx >= count) return -1;
        ListNode node = dummyHead;
        for (int i = 0; i <= idx; i++) {
            node = node.next;
        }
        return node.val;
    }

    public void addAtHead(int v) {
        addAtIndex(0, v);
    }

    public void addAtTail(int v) {
        addAtIndex(count, v);
    }

    public void addAtIndex(int idx, int v) {
        if (idx > count) return;
        if (idx < 0) idx = 0;
        count++;
        ListNode predecessor = dummyHead;
        for (int i = 0; i < idx; i++) {
            predecessor = predecessor.next;
        }
        ListNode nodeToInsert = new ListNode(v);
        nodeToInsert.next = predecessor.next;
        predecessor.next = nodeToInsert;
    }

    public void deleteAtIndex(int idx) {
        if (idx < 0 || idx >= count) return;
        count--;
        ListNode predecessor = dummyHead;
        for (int i = 0; i < idx; i++) {
            predecessor = predecessor.next;
        }
        predecessor.next = predecessor.next.next;
    }
}

206. Reverse Linked List

Reverse a singly linked list.

public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = previous;
        previous = current;
        current = nextTemp;
    }
    return previous;
}

24. Swap Nodes in Pairs

Swap every two adajcent nodes in a linked list.

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode secondNode = head.next;
    ListNode swappedRemaining = swapPairs(secondNode.next);
    secondNode.next = head;
    head.next = swappedRemaining;
    return secondNode;
}

19. Remove Nth Node From End of List

Remove the nth node from the end of the list.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode sentinel = new ListNode(0, head);
    ListNode fast = sentinel;
    ListNode slow = sentinel;
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return sentinel.next;
}

Intersection of Two Linked Lists

Find the node where two singly linked lists intersect.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> visited = new HashSet<>();
    ListNode ptr = headA;
    while (ptr != null) {
        visited.add(ptr);
        ptr = ptr.next;
    }
    ptr = headB;
    while (ptr != null) {
        if (visited.contains(ptr)) return ptr;
        ptr = ptr.next;
    }
    return null;
}

142. Linked List Cycle II

Return the node where a cycle begins in a linked list, or null if no cycle exists.

public ListNode detectCycle(ListNode head) {
    Set<ListNode> nodeSet = new HashSet<>();
    while (head != null) {
        if (nodeSet.contains(head)) {
            return head;
        }
        nodeSet.add(head);
        head = head.next;
    }
    return null;
}