1. Find the intersection of two linked lists
160. Intersection of Two Linked Lists (Easy)
Let the length of A be a + c and the length of B be b + c, where c is the length of the common part of the tail. It can be seen that a + c + b = b + c + a.
When the pointer accessing the list A accesses the tail of the list, make it access the list B from the head of the list B; Similarly, when the pointer accessing the B linked list accesses the tail of the linked list, make it access linked list A from the head of linked list A. In this way, you can control the pointer to access the two linked lists A and B, and access the intersection at the same time.
If they have the same speed and the same distance at the same time, they will reach the end at the same time.
If there is no intersection, then a + b = b + a, l1 and l2 in the following implementation code will be null at the same time, thus exiting the loop.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
2. Linked list inversion
206. Reverse Linked List (Easy)
Recursion:
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode next = head.next;
ListNode newHead = reverseList(next);// The recursive call starts from the next node of the current node.
next.next = head;// Hanging the head behind the next node completes the inversion of the linked list.
head.next = null;// Here, the head is equivalent to becoming a tail node. The tail nodes are empty, otherwise it will form a ring.
return newHead;
}
Head insertion method:
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newHead.next;
newHead.next = head;
head = next;
}
return newHead.next;
}
Double pointer:
public ListNode reverseList(ListNode head) {
ListNode cur = head, end = null;
while (cur != null) {
ListNode tmp = cur.next;// The original linked list node accessed each time will become the head node of the new linked list
cur.next = end;
end = cur;// Update new linked list
cur = tmp;
}
return end;
}
3. Merge two ordered linked lists
21. Merge Two Sorted Lists (Easy)
Recursion:
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;
}
}
Iteration:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1 != null && l2!= null){
if(l1.val <= l2.val){
cur.next = l1;
l1 = l1.next;
}else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 == null) ? l2 : l1;
return dummy.next;
}
4. Circular linked list
141. Linked List Cycle(Easy)
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;
}
5. Palindrome linked list
234. Palindrome Linked List (Easy)
Subject requirements: solve with the spatial complexity of O(1).
"Speed pointer":
- Find the tail node of the first half of the linked list.
- Reverse the second half of the linked list.
- Determine whether to reply.
- Restore the linked list.
- Returns the result.
public boolean isPalindrome2(ListNode head) {
// 1 - > 2 - > 2 - > 1 - > null = > 1 - > 2 - > 2 - > 1 - > null = > 1 - > 2 null < - 2 < - 1 (even nodes)
// s/f s f h s
// 1 - > 2 - > 3 - > 2 - > 1 - > null = > 1 - > 2 - > 3 - > 2 - > 1 - > null = > 1 - > 2 3 < - 2 < - 1 (odd nodes)
// s/f s f h s
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) slow = slow.next;
slow = reverse(slow);
while (slow != null && head.val == slow.val) {
head = head.next;
slow = slow.next;
}
return slow == null;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
6. Delete duplicate nodes from the ordered linked list
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
Recursion:
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
Iteration:
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null) {
if (cur.next == null) break;
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
7. Delete the penultimate node of the linked list
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
"Speed pointer":
public ListNode removeNthFromEnd(ListNode head, int n) {
// 1,2,3,4,5,null => 1,2,3,4,5,null n = 2
// p q p q
ListNode p = head, q = head;
while (n-- > 0) q = q.next;
if(q == null) return q.next;
while (q.next != null) {
q = q.next;
p = p.next;
}
// 1,2,3,5,null
p.next = p.next.next;
return head;
}
8. Exchange of adjacent nodes in the linked list
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
Topic requirements: the val value of the node cannot be modified, O(1) space complexity.
Recursion:
- Time complexity O(n), space complexity O(n)
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
Iteration:
- Time complexity O(n), space complexity O(1)
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode temp = dummyHead;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
temp.next = node2;
node1.next = node2.next;
node2.next = node1;
temp = node1;
}
return dummyHead.next;
}
9. Add two numbers II
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
Title Requirements: the original linked list cannot be modified.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = buildStack(l1);
Stack<Integer> l2Stack = buildStack(l2);
ListNode head = new ListNode(-1);
int carry = 0;
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carry = sum / 10;
}
return head.next;
}
private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}
10. Separate linked list
725. Split Linked List in Parts(Medium)
Title Requirements: divide the linked list into k parts. The length of each part should be the same as possible, and the length in the front should be greater than or equal to that in the back.
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] parts = new ListNode[k];
int len = 0;
for (ListNode node = root; node != null; node = node.next)
len++;
int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
ListNode node = root, prev = null;
for (int i = 0; node != null && i < k; i++, r--) {
parts[i] = node;
for (int j = 0; j < n + (r > 0 ? 1 : 0); j++) {
prev = node;
node = node.next;
}
prev.next = null;
}
return parts;
}
11. Linked list elements are clustered by parity
328. Odd Even Linked List (Medium)
Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.
Topic requirements: the spatial complexity of the algorithm should be O(1), the time complexity should be O(n), and N is the total number of nodes.
public ListNode oddEvenList(ListNode head) {
// Separate the linked list according to parity, and then merge the linked list
// 1->2->3->4->5->null => 1->3->5 2->4->null => 1->3->5->2->4->null
if(head == null || head.next == null) return head;
ListNode odd = head, even = head.next, evenHead = even;
while(odd.next != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
12. Circular linked list II
142. Linked List Cycle II (Medium)
Advanced topic: spatial complexity O(1)
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
// Double pointer: speed fast = 2*slow, starting from head at the same time, set the entry point as p and the meeting point as w
// |p
// 3 -> 2 -> 0 -> 4 -> 1
// \ /
// 4 <- 6 <- 5
// |w
// Distance: head - > P: A, P - > W: B, W - > P: C
// slow : A + B, fast = A + 2B + C => A = C
// Therefore, after meeting, slow continues to run from the meeting point with fast to the ring entry point (C), and another slow2 just meets slow at the ring entry point (A)
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
while (slow == fast) {
ListNode slow2 = head;
while (slow != slow2) {
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
13. LRU cache mechanism
146. LRU Cache(Medium)
public class LRUCache {
private int capacity;
private int size;
private DLinkedNode head, tail;
private Map<Integer, DLinkedNode> cache = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
// Pseudo header and pseudo tail mark boundaries
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// The key exists. First locate it through the hash table, and then move it to the header
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// key does not exist. Create a new node in the header of the double chain
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
++size;
// Super capacity, delete the tail node of the double linked list, and delete the corresponding item in the hash table
if (size > capacity) {
DLinkedNode tail = removeTail();
cache.remove(tail.key);
--size;
}
// Locate the hash table, modify the value and move it to the head
} else {
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
node.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
class DLinkedNode {
public int key;
public int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
14. Copy the linked list with random pointer
138. Copy List with Random Pointer(Medium)
to flash back:
- Time complexity O(n) space complexity O(n)
public Node copyRandomList1(Node head) {
if (head == null) return null;
// If we have processed the current node, we only need to return its cloned version.
if (this.visited.containsKey(head)) {
return this.visited.get(head);
}
// Create a new node with the same value as the old node (that is, the replication node).
Node node = new Node(head.val, null, null);
// Save this value in HashMap. Because the randomness of random pointers may lead to loops in the traversal process, it will help us avoid loops here.
this.visited.put(head, node);
// Recursively copy the remaining linked list from the next pointer, and then recursively copy from the random pointer.
// So we have two separate recursive calls, and finally we update the next pointer and random pointer for the new node we create.
node.next = this.copyRandomList1(head.next);
node.random = this.copyRandomList1(head.random);
return node;
}
Advanced:
- Time complexity O(n) space complexity O(1)
public Node copyRandomList(Node head) {
if (head == null) return null;
// ----— ----------— -----—
// | | | | | |
// 1 -> 2 -> 3 -> 4 => 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4' => 1' -> 2' -> 3' -> 4'
// | | | | | |
// ----— ----------— -----—
// Step 1: place each copy node next to the original corresponding node.
Node iter = head, next;
while (iter != null) {
next = iter.next;
Node copy = new Node(iter.val);
iter.next = copy;
copy.next = next;
iter = next;
}
// Step 2: assign a random pointer to the copy node.
iter = head;
while (iter != null) {
if (iter.random != null) {
iter.next.random = iter.random.next;
}
iter = iter.next.next;
}
// Step 3: restore the original linked list and extract the cloned linked list.
iter = head;
Node pseudoHead = new Node(0);
Node copy, copyIter = pseudoHead;
while (iter != null) {
next = iter.next.next;
// Extract clone linked list
copy = iter.next;
copyIter.next = copy;
copyIter = copy;
// Save the original linked list
iter.next = next;
iter = next;
}
return pseudoHead.next;
}
class Node {
int val;
Node next;
Node random;
public Node(int val, Node next, Node random) {
this.val = val;
this.next = next;
this.random = random;
}
public Node(int val) {
this.val = val;
}
}
15. Turn over the linked list in groups of K
25. Reverse Nodes in k-Group(Hard)
Topic requirements: additional space using constants; Instead of simply changing the internal value of the node, you need to actually exchange nodes.
public ListNode reverseKGroup1(ListNode head, int k) {
ListNode dummy = new ListNode(0);
// 1->2->3->4->5 k=2
// 1. Declare a dummy node dummy
dummy.next = head;
// 2.pre and end point to the same precursor node
ListNode pre = dummy, end = dummy;
while (end.next != null) {
// 3. Get the flipped linked list fragment start - >... - > end
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
ListNode next = end.next;
// Isolate linked list segments that need to be flipped
end.next = null;
ListNode start = pre.next;
// 4. Flip the linked list dummy - > end - >... - > start
pre.next = reverse(pre);
// 5. Connect the flipped linked list, and pre and end point to the same precursor node
start.next = next;
pre = start;
end = pre;
}
return dummy.next;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}