Linked List Pattern
Linked Lists are fundamental data structures that consist of nodes connected by pointers. They’re particularly useful for:
- Dynamic memory allocation
- Efficient insertions and deletions
- Implementing other data structures
- Memory-efficient storage
- Circular data structures
1. Reverse Linked List (Easy)
Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.
Solution:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1)
2. Merge Two Sorted Lists (Easy)
Problem: Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Solution:
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}Time Complexity: O(n + m) where n and m are lengths of input lists Space Complexity: O(1)
3. Reorder List (Medium)
Problem: Given the head of a singly linked list L: L0 → L1 → … → Ln-1 → Ln, reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
Solution:
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Find middle
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode prev = null, curr = slow;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Merge two halves
ListNode first = head, second = prev;
while (second.next != null) {
ListNode temp = first.next;
first.next = second;
first = temp;
temp = second.next;
second.next = first;
second = temp;
}
}
}Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1)
4. 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.
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 end
while (first != null) {
first = first.next;
second = second.next;
}
// Remove the nth node
second.next = second.next.next;
return dummy.next;
}
}Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1)
5. 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.
Solution:
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
// Step 1: Create copy nodes next to original nodes
Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
// Step 2: Set random pointers
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate original and copy lists
Node dummy = new Node(0);
Node copyCurr = dummy;
curr = head;
while (curr != null) {
copyCurr.next = curr.next;
curr.next = curr.next.next;
curr = curr.next;
copyCurr = copyCurr.next;
}
return dummy.next;
}
}Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1)
6. 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.
Solution:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = 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;
curr.next = new ListNode(sum % 10);
curr = curr.next;
}
return dummy.next;
}
}Time Complexity: O(max(n,m)) where n and m are lengths of input lists Space Complexity: O(max(n,m))
7. Linked List Cycle (Easy)
Problem: Given head, the head of a linked list, determine if the linked list has a cycle in it.
Solution:
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) where n is the number of nodes Space Complexity: O(1)
8. Find the Duplicate Number (Medium)
Problem: Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, find the duplicate number.
Solution:
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
// Find meeting point
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// Find entrance to cycle
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}Time Complexity: O(n) where n is the length of the array Space Complexity: O(1)
9. LRU Cache (Medium)
Problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Solution:
class LRUCache {
private class Node {
int key, value;
Node prev, next;
Node(int k, int v) {
key = k;
value = v;
}
}
private Map<Integer, Node> cache;
private Node head, tail;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
remove(node);
add(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
remove(cache.get(key));
}
if (cache.size() == capacity) {
remove(tail.prev);
}
add(new Node(key, value));
}
private void add(Node node) {
cache.put(node.key, node);
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) {
cache.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}
}Time Complexity: O(1) for both get and put operations Space Complexity: O(capacity)
10. 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.
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);
for (ListNode list : lists) {
if (list != null) {
pq.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
curr.next = node;
curr = curr.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) for the priority queue
11. Reverse Nodes in K Group (Hard)
Problem: Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
Solution:
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
ListNode tail = prev;
// Check if there are k nodes left
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) return dummy.next;
}
ListNode next = tail.next;
ListNode[] reversed = reverse(head, tail);
head = reversed[0];
tail = reversed[1];
// Connect the reversed group
prev.next = head;
tail.next = next;
prev = tail;
head = next;
}
return dummy.next;
}
private ListNode[] reverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode curr = head;
while (prev != tail) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return new ListNode[]{tail, head};
}
}Time Complexity: O(n) where n is the number of nodes Space Complexity: O(1)
Key Takeaways
-
Linked List is perfect for:
- Dynamic memory allocation
- Efficient insertions and deletions
- Implementing other data structures
- Memory-efficient storage
- Circular data structures
-
Common patterns:
- Two pointer technique (fast & slow)
- Dummy node for edge cases
- Reversing linked lists
- Merging sorted lists
- Cycle detection
-
Tips:
- Always check for null pointers
- Use dummy nodes to handle edge cases
- Consider using two pointers for complex operations
- Think about space-time tradeoffs
- Consider using sentinel nodes
Comments