Linked List
Java solutions with explanations, time and space complexity for Linked List problems from Blind 75.
Linked List
This section covers problems that involve linked list manipulation, traversal, and common linked list operations.
1. Reverse Linked List (Easy)
Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.
Example:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Solution:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}Time Complexity: O(n) Space Complexity: O(1)
Recursive Approach:
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}Time Complexity: O(n) Space Complexity: O(n) - due to recursion stack
2. Merge Two Sorted Lists (Easy)
Problem: You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Solution:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
// Attach remaining nodes
current.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}Time Complexity: O(n + m) Space Complexity: O(1)
3. Linked List Cycle (Easy)
Problem: Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Example:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).Solution:
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
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;
}
}Time Complexity: O(n) Space Complexity: O(1)
Key Insight: Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)
4. Reorder List (Medium)
Problem: You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example:
Input: head = [1,2,3,4]
Output: [1,4,2,3]Solution:
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Find the middle
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
ListNode second = reverseList(slow.next);
slow.next = null;
// Merge the two halves
ListNode first = head;
while (second != null) {
ListNode temp1 = first.next;
ListNode temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}Time Complexity: O(n) Space Complexity: O(1)
5. Remove Nth Node From End of List (Medium)
Problem: Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]Solution:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Move first pointer n+1 steps ahead
for (int i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until first reaches the end
while (first != null) {
first = first.next;
second = second.next;
}
// Remove the nth node from end
second.next = second.next.next;
return dummy.next;
}
}Time Complexity: O(n) Space Complexity: O(1)
Key Insight: Use two pointers with n+1 gap to find the node before the one to be removed.
6. Merge K Sorted Lists (Hard)
Problem: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]Solution:
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// Add first node of each list to priority queue
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
current.next = node;
current = current.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
}Time Complexity: O(n log k) where n is total number of nodes and k is number of lists Space Complexity: O(k)
Alternative Approach (Divide and Conquer):
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeKListsHelper(lists, 0, lists.length - 1);
}
private ListNode mergeKListsHelper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
if (start > end) {
return null;
}
int mid = start + (end - start) / 2;
ListNode left = mergeKListsHelper(lists, start, mid);
ListNode right = mergeKListsHelper(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}Time Complexity: O(n log k) Space Complexity: O(log k) - recursion stack
7. Copy List with Random Pointer (Medium)
Problem: A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next pointer and the random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.
Example:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]Solution:
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
// Step 1: Create copy nodes and insert them after original nodes
Node current = head;
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Set random pointers for copy nodes
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Step 3: Separate original and copy lists
Node dummy = new Node(0);
Node copyCurrent = dummy;
current = head;
while (current != null) {
copyCurrent.next = current.next;
copyCurrent = copyCurrent.next;
current.next = current.next.next;
current = current.next;
}
return dummy.next;
}
}Time Complexity: O(n) Space Complexity: O(1) - excluding the output list
8. Add Two Numbers (Medium)
Problem: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
Example:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.Solution:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}
return dummy.next;
}
}Time Complexity: O(max(n, m)) Space Complexity: O(max(n, m))
Key Takeaways
- Two Pointers: Use fast and slow pointers for cycle detection
- Dummy Node: Use dummy nodes to handle edge cases
- Reverse Operations: Master linked list reversal for many problems
- Merge Operations: Understand how to merge sorted linked lists
- Pointer Manipulation: Be careful with pointer assignments
- Memory Management: Consider space complexity when using recursion