Node Class Definition
The following ListNode class serves as the foundation for all examples in this article:
import java.util.Arrays;
public class ListNode {
int data;
ListNode next = null;
public ListNode(int data) {
this.data = data;
}
public String toString(ListNode node) {
int[] values = new int[calculateSize(node)];
int index = 0;
while (node != null) {
values[index++] = node.data;
node = node.next;
}
return Arrays.toString(values);
}
public int calculateSize(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
}
Finding the Kth Node from the End
Problem Description
Given a linked list, return the kth node from the end. If the list length is less than k, return null.
Example 1:
Input: {1,2,3,4,5}, k=2
Output: {4,5}
Example 2:
Input: {2}, k=8
Output: {}
Solution 1: Calculate Length First
First compute the total length of the list, then calculate how many steps to traverse from the head to reach the target node.
public ListNode findKthFromEnd(ListNode head, int k) {
int size = calculateSize(head);
if (size < k) {
return null;
}
int stepsToMove = size - k;
while (stepsToMove > 0) {
head = head.next;
stepsToMove--;
}
return head;
}
private int calculateSize(ListNode node) {
int count = 0;
while (node != null) {
count++;
node = node.next;
}
return count;
}
Solution 2: Two-Pointer Technique
Use a fast pointer that moves k steps ahead first. Then both pointers move together until the fast pointer reaches the end. The slow pointer will then be at the kth node from the end.
public ListNode findKthFromEndTwoPointers(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// Fast pointer moves k steps ahead
while (k > 0) {
if (fast == null) {
return null; // k exceeds list length
}
fast = fast.next;
k--;
}
// Both pointers move together
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
Removing Duplicate Nodes from Sorted List
Problem Description
In a sorted linked list, delete all nodes that have duplicates (keep only nodes that appear exactly once).
Example 1:
Input: {1,2,3,3,4,4,5}
Output: {1,2,5}
Example 2:
Input: {1,1,1,8}
Output: {8}
Solutino Approach
Use a dummy head node to simplify edge cases. Maintain a previous pointer for builidng the result list and a current pointer to scan for duplicates. When duplicates are found, skip all of them and connect the previous pointer to the next unique node.
public ListNode removeDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.data == curr.next.data) {
// Skip all duplicate nodes
while (curr.next != null && curr.data == curr.next.data) {
curr = curr.next;
}
curr = curr.next;
prev.next = curr;
} else {
prev = curr;
curr = curr.next;
}
}
return dummyHead.next;
}
Copying a Complex Linked List
Problem Description
A complex linked list has two pointers: next pointing to the next node, and random pointing to any random node in the list. Create a deep copy of this list.
Solution Approach
The algorithm follows three steps:
- Clone each node and insert it immediately after its original node
- Copy the random pointers for each cloned node
- Split the combined list into two separate lists
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public RandomListNode copyComplexList(RandomListNode head) {
if (head == null) {
return null;
}
// Step 1: Clone each node and insert after original
RandomListNode current = head;
while (current != null) {
RandomListNode cloned = new RandomListNode(current.label);
cloned.next = current.next;
current.next = cloned;
current = cloned.next;
}
// Step 2: Copy random pointers
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Split the lists
current = head;
RandomListNode clonedHead = head.next;
while (current != null) {
RandomListNode cloned = current.next;
current.next = cloned.next;
if (cloned.next != null) {
cloned.next = cloned.next.next;
}
current = current.next;
}
return clonedHead;
}
Deleting the Middle Node
Problem Description
Delete the middle node of a linked list. For a list of length n, the middle node is at index ⌊n/2⌋ (0-indexed).
Example:
Input: [1,3,4,7,1,2,6] (length 7, middle index 3)
Output: [1,3,4,1,2,6]
Solution: Fast-Slow Pointer with Dummy Head
Use a dummy head to simplify deletion. The fast pointer moves two steps while the slow pointer moves one step. When the fast pointer reaches the end, the slow pointer is at the node before the middle node.
public ListNode deleteMiddle(ListNode head) {
if (head == null) {
return null;
}
ListNode dummyHead = new ListNode(-1, head);
ListNode fast = head;
ListNode slow = dummyHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
Removing the Nth Node from the End
Problem Description
Remove the nth node from the end of a linked list and return the head.
Example:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Solution: Calculate Length Approach
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = getSize(head);
ListNode dummyHead = new ListNode(-1, head);
ListNode current = dummyHead;
int steps = length - n;
for (int i = 0; i < steps; i++) {
current = current.next;
}
current.next = current.next.next;
return dummyHead.next;
}
private int getSize(ListNode node) {
int count = 0;
while (node != null) {
count++;
node = node.next;
}
return count;
}