Intersection of Two Linked Lists
To determine the node where two singly-linked lists intersect, one can utilize a dual-pointer technique that accounts for the difference in lengths. By swapping the pointers when they reach the end of their respective lists, both pointers effectively traverse the combined length of the two lists. This synchronization ensures they meet at the intersection node or simultaneously reach null.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA == null) ? headB : pA.next;
pB = (pB == null) ? headA : pB.next;
}
return pA;
}Reverse Linked List
Iterative Approach: This method involves traversing the list while reversing the links between nodes. A variable tracks the previous node, allowing the current node to point backwards instead of forwards.
public ListNode reverseList(ListNode head) {
ListNode current = head, previous = null;
while (current != null) {
ListNode nextTemp = current.next;
current.next = previous;
previous = current;
current = nextTemp;
}
return previous;
}Recursive Approach: The recursive solution dives to the end of the list and then reverses the links as the recursion stack unwinds. The node following the current head is linked back to the head, and the head's forward link is severed.
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;
}Palindrome Linked List
Checking for a palindrome requires comparing the first half of the list with the reversed second half. First, locate the middle of the list using the fast and slow pointer technique. Reverse the second half and then compare it node by node with the first half.
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reversedHalf = reverseList(slow);
ListNode p1 = head, p2 = reversedHalf;
while (p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}Linked List Cycle Detection
The presence of a cycle can be detected using two pointers moving at different speeds. If there is a cycle, the faster pointer will eventually catch up to the slower one. If the list terminates, the fast pointer will reach null.
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head, fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}Linked List Cycle II
Once a cycle is detected, finding the entry point requires a second phase. Reset one pointer to the head and keep the other at the meeting point. Moving both at the same speed will cause them to converge at the cycle's start node.
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (true) {
if (fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}Merge Two Sorted Lists
Iterative Merging: Use a dummy node to simplify edge cases. Iterate through both lists, appending the smaller node to the result list until one list is exhausted, then append the remainder of the other list.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 == null) ? l2 : l1;
return dummy.next;
}Recursive Merging: Recursively compare the heads of the lists. The smaller head becomes the next node of the result, and the function calls itself with the remaining sublists.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}Add Two Numbers
Addition is performed digit by digit, starting from the heads of the two lists. A carry variable tracks values that overflow the current digit position. The loop continues until both lists and the carry are exhausted.
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 x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}Remove Nth Node From End of List
A dummy node is used to handle cases where the head needs to be removed. Two pointers are initialized: one advances N steps ahead, then both move until the leading pointer reaches the end. The trailing pointer, which is N steps behind, will be positioned just before the target node.
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode leader = dummy, follower = dummy;
for (int i = 0; i <= n; i++) {
leader = leader.next;
}
while (leader != null) {
leader = leader.next;
follower = follower.next;
}
follower.next = follower.next.next;
return dummy.next;
}Swap Nodes in Pairs
Nodes are swapped in groups of two. A dummy node helps anchor the head of the list. The loop iterates while there are at least two nodes remaining to swap.
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode first = prev.next;
ListNode second = prev.next.next;
prev.next = second;
first.next = second.next;
second.next = first;
prev = first;
}
return dummy.next;
}Reverse Nodes in k-Group
This problem requires reversing every k consecutive nodes. If the remaining nodes are fewer than k, they remain unchanged. The process involves identifying the sub-list to reverse, reversing it, and reconnecting it to the main list.
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode prevGroupEnd = dummy;
while (true) {
ListNode kthNode = prevGroupEnd;
for (int i = 0; i < k; i++) {
kthNode = kthNode.next;
if (kthNode == null) return dummy.next;
}
ListNode nextGroupStart = kthNode.next;
ListNode[] reversed = reverse(prevGroupEnd.next, kthNode);
prevGroupEnd.next = reversed[0];
reversed[1].next = nextGroupStart;
prevGroupEnd = reversed[1];
}
}
private ListNode[] reverse(ListNode start, ListNode end) {
ListNode prev = end.next;
ListNode curr = start;
while (curr != end) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
end.next = prev;
return new ListNode[]{end, start};
}LRU Cache Mechanism
Implementing an LRU cache combines a hash map for O(1) access and a doubly linked list to manage recency. The most recently accessed items are moved to the head (front), and when capacity is exceeded, the least recently used item at the tail is removed.
class LRUCache {
class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private int cap;
private Map map;
private Node head, tail;
public LRUCache(int capacity) {
cap = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node);
insert(node);
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) remove(map.get(key));
Node node = new Node(key, value);
map.put(key, node);
insert(node);
if (map.size() > cap) {
Node lru = tail.prev;
remove(lru);
map.remove(lru.key);
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insert(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
} Sort List
Sorting a linked list is efficiently handled using Merge Sort. The list is recursively split into halves until single nodes remain, then merged back together in sorted order.
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
return merge(sortList(head), sortList(mid));
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 == null) ? l2 : l1;
return dummy.next;
}Merge K Sorted Lists
Merging multiple sorted lists is an extension of merging two lists. A divide-and-conquer approach efficiently combines pairs of lists recursively until a single sorted list remains.
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
return partition(lists, 0, lists.length - 1);
}
private ListNode partition(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];
int mid = start + (end - start) / 2;
ListNode l1 = partition(lists, start, mid);
ListNode l2 = partition(lists, mid + 1, end);
return merge(l1, l2);
}