Singly Linked List

Most common type. F/S pointers are popular.

Definition

private class Node {
    int value;
    Node nextNode;
    public Node(int value) {
        this.value = value;
        nextNode = null;
    }
}

Basic Operations

Add

if (current.nextNode == null) {
    current.nextNode = newNode;
}

or

prev.next = newNode;
newNode.next = current;

Delete

if (current.value == target) {
    prev.next = current.next;
}

Reverse

public ListNode reverseList(ListNode head) {
    ListNode prev = null, current = head, temp;
    while (current != null) {
        temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}

Dummy Head

If we want to modify the head of a linked list, using a dummy head node will make the job easier (avoid the special case for head).

ListNode dummy = new ListNode(0);
dummy.next = head;
...
return dummy.next;

Find midpoint

Delete Node in the Middle of Singly Linked List

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

slow stops at the middle if the length is odd and stops at length/2 + 1 if the length is even.