Linked Lists

Overview

Linked-list problems test pointer ownership more than indexing. Nodes are reached by following links, so insertions and deletions are constant time once the relevant predecessor is known, while random access is linear.

Most mistakes come from overwriting a link before saving it. Use a dummy head when the real head may change, preserve next before mutation, and draw the pointer relationships for reversal or reordering. Slow/fast pointers handle middle, cycle, and distance-from-end problems without extra storage.

Templates

Reverse a list

  • Initialize prev = null and curr = head.
  • Save next = curr.next.
  • Redirect curr.next = prev.
  • Advance prev = curr and curr = next.
  • Return prev.
public class LinkedListTemplates {
	public ListNode reverse(ListNode head) {
		ListNode prev = null;
		ListNode curr = head;

		while (curr != null) {
			ListNode next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}

		return prev;
	}
}

Find the first middle

  • Initialize slow = head and fast = head.
  • While both fast.next and fast.next.next exist, advance slow by one node and fast by two.
  • Return slow. This condition returns the first middle for an even-length list and the only middle for an odd-length list.
public class LinkedListTemplates {
	public ListNode firstMiddle(ListNode head) {
		if (head == null) {
			return null;
		}

		ListNode slow = head;
		ListNode fast = head;

		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		return slow;
	}
}

Find the second middle

  • Initialize slow = head and fast = head.
  • While both fast and fast.next exist, advance slow by one node and fast by two.
  • Return slow. This condition returns the second middle for an even-length list and the only middle for an odd-length list.
public class LinkedListTemplates {
	public ListNode secondMiddle(ListNode head) {
		ListNode slow = head;
		ListNode fast = head;

		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		return slow;
	}
}

Delete all nodes with a target value

  • Create a dummy node before head, then initialize prev = dummy and curr = head.
  • While curr exists, save next = curr.next before changing any links.
  • If curr.val == target, delete curr with prev.next = next and keep prev in place.
  • Otherwise, retain curr and advance prev = curr.
  • Advance curr = next, then return dummy.next.
public class LinkedListTemplates {
	public ListNode deleteTarget(ListNode head, int target) {
		ListNode dummy = new ListNode(0, head);
		ListNode prev = dummy;
		ListNode curr = head;

		while (curr != null) {
			ListNode next = curr.next;

			if (curr.val == target) {
				prev.next = next;
			} else {
				prev = curr;
			}

			curr = next;
		}

		return dummy.next;
	}
}

Problems

19. Remove Nth Node From End of List

Remove the nth node from the end in one pass. Start slow and fast at a dummy node, then advance fast by n + 1 links. While fast != null, advance both pointers by one node. When the loop ends, slow.next is the node to remove, so bypass it with slow.next = slow.next.next.

class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode dummy = new ListNode(0, head);
		ListNode slow = dummy;
		ListNode fast = dummy;

		for (int step = 0; step <= n; step++) {
			fast = fast.next;
		}

		while (fast != null) {
			slow = slow.next;
			fast = fast.next;
		}

		slow.next = slow.next.next;
		return dummy.next;
	}
}

141. Linked List Cycle

Detect whether following next pointers eventually revisits a node. Floyd’s tortoise-and-hare algorithm advances one pointer by one node and another by two; in a cycle, the faster pointer must eventually meet the slower one.

class Solution {
	public boolean hasCycle(ListNode head) {
		ListNode slow = head;
		ListNode fast = head;

		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			if (slow == fast) {
				return true;
			}
		}

		return false;
	}
}

2. Add Two Numbers

Add two non-negative integers whose digits are stored in reverse order in linked lists. Traverse both lists together and use has1 to carry a one into the next position. Each iteration reads the available digits, separates their sum into the next carry and output digit, then appends that digit to the result. Continue while either list has a node or has1 remains. The solution takes O(max(m, n)) time and uses O(max(m, n)) space for the output list.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        int has1 = 0;

        while (l1 != null || l2 != null || has1 != 0) {
            int d1 = 0;
            int d2 = 0;

            if (l1 != null) {
                d1 = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                d2 = l2.val;
                l2 = l2.next;
            }

            int sum = d1 + d2 + has1;
            has1 = sum / 10;
            int val = sum % 10;
            curr.next = new ListNode(val);
            curr = curr.next;
        }

        return dummy.next;
    }
}

143. Reorder List

Rearrange L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → …. Find the first middle node, reverse the second half, split the list after the middle, then alternate nodes from the two halves. Each phase is linear and uses constant extra space.

class Solution {
    public void reorderList(ListNode head) {
        ListNode firstMid = findMid(head);
        ListNode reverseHead = reverseList(firstMid.next);
        firstMid.next = null;
        ListNode node1 = head;
        ListNode node2 = reverseHead;

        while (node1 != null && node2 != null) {
            ListNode tmp1 = node1.next;
            ListNode tmp2 = node2.next;
            node1.next = node2;
            node2.next = tmp1;
            node1 = tmp1;
            node2 = tmp2;
        }
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nxxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxxt;
        }

        return prev;
    }
}

86. Partition List

Partition the list so every node with a value less than x appears before every node with a value greater than or equal to x, while preserving relative order within both groups. Build separate less and more chains, terminate the more chain to remove any stale link, then join the two chains. The solution runs in O(n) time and uses O(1) extra space.

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyLess = new ListNode();
        ListNode currLess = dummyLess;
        ListNode dummyMore = new ListNode();
        ListNode currMore = dummyMore;

        ListNode curr = head;
        while (curr != null) {
            if (curr.val < x) {
                currLess.next = curr;
                currLess = curr;
            } else {
                currMore.next = curr;
                currMore = curr;
            }
            curr = curr.next;
        }

        currLess.next = dummyMore.next;
        dummyMore.next = null;
        // don't forget this!
        currMore.next = null;
        return dummyLess.next;
    }
}

2487. Remove Nodes From Linked List

Remove every node that has a greater value somewhere to its right. Reverse the list so the original right side is processed first, track the maximum value seen, and delete every node below that maximum using the standard prev and curr pattern. Reverse the filtered list to restore its original direction. The solution runs in O(n) time and uses O(1) extra space.

class Solution {
    public ListNode removeNodes(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode reverseHead = reverseList(head);
        ListNode dummy = new ListNode(0, reverseHead);
        ListNode prev = dummy;
        ListNode curr = reverseHead;
        int maxVal = Integer.MIN_VALUE;

        // Below is the standard pattern to delete nodes
        while (curr != null) {
            maxVal = Math.max(curr.val, maxVal);
            if (curr.val < maxVal) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }

        return reverseList(dummy.next);
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        return prev;
    }
}

92. Reverse Linked List II

Reverse only the nodes from positions left through right. Use a dummy node so reversing from the head needs no special case, advance prev and curr to the start of the range, reverse exactly right - left links, then reconnect both ends of the reversed segment. The solution runs in O(n) time and uses O(1) extra space.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode curr = head;

        for (int i = 0; i < left - 1; i++) {
            prev = curr;
            curr = curr.next;
        }

        ListNode start = prev;
        prev = curr;
        curr = curr.next;

        for (int i = 0; i < right - left; i++) {
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        start.next.next = curr;
        start.next = prev;

        return dummy.next;
    }
}

25. Reverse Nodes in k-Group

Reverse the list in consecutive groups of k nodes while leaving an incomplete final group unchanged. Before each reversal, verify that k nodes remain after prev_tail. Reverse exactly those nodes, reconnect the previous group to the new head, connect the new tail to the next group, and advance prev_tail. The solution runs in O(n) time and uses O(1) extra space.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode prevTail = dummy;

        while (true) {
            if (!hasNextK(prevTail, k)) {
                break;
            }

            ListNode[] group = reverseNextK(prevTail, k);
            ListNode currHead = group[0];
            ListNode nextHead = group[1];
            ListNode currTail = prevTail.next;
            prevTail.next = currHead;
            currTail.next = nextHead;
            prevTail = currTail;
        }

        return dummy.next;
    }

    private ListNode[] reverseNextK(ListNode node, int k) {
        ListNode prev = node;
        ListNode curr = node.next;
        int i = k;

        while (i > 0) {
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
            i--;
        }

        return new ListNode[] {prev, curr};
    }

    // Given a node, whether there are k nodes AFTER node
    private boolean hasNextK(ListNode node, int k) {
        int i = k;

        while (i > 0) {
            node = node.next;
            if (node == null) {
                break;
            }
            i--;
        }

        return i == 0;
    }
}