# 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) {

while (p1 != p2) {
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
```

Recursion:

```public ListNode reverseList(ListNode head) {

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.

}
```

```public ListNode reverseList(ListNode head) {
}
}
```

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;
}
```

```    public boolean hasCycle(ListNode head) {

while (slow != fast) {
if (fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
```

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.
• 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
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) {
slow = slow.next;
}
return slow == null;
}

ListNode prev = null;
}
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) {
}
```

Iteration:

```    public ListNode deleteDuplicates(ListNode head) {

while(cur != null) {
if (cur.next == null) break;
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
}
```

# 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
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;
}
```

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) {
}
}
```

Iteration:

• Time complexity O(n), space complexity O(1)
```	public ListNode swapPairs(ListNode head) {
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;
}
}
```

# 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);
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);
carry = sum / 10;
}
}

private Stack<Integer> buildStack(ListNode l) {
Stack<Integer> stack = new Stack<>();
while (l != null) {
stack.push(l.val);
l = l.next;
}
return stack;
}
```

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

while(odd.next != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
}
```

# 12. Circular linked list II

142. Linked List Cycle II (Medium)

```    public ListNode detectCycle(ListNode head) {
// 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)
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
while (slow == fast) {
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 Map<Integer, DLinkedNode> cache = new HashMap<>();

public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
// Pseudo header and pseudo tail mark boundaries
}

public int get(int key) {
if (node == null) {
return -1;
}
// The key exists. First locate it through the hash table, and then move it to the header
return node.value;
}

public void put(int key, int value) {
if (node == null) {
// key does not exist. Create a new node in the header of the double chain
cache.put(key, 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) {
cache.remove(tail.key);
--size;
}
// Locate the hash table, modify the value and move it to the head
} else {
node.value = value;
}
}

node.next.prev = node;
}

node.prev.next = node.next;
node.next.prev = node.prev;
}

removeNode(node);
}

removeNode(res);
return res;
}
}

public int key;
public int value;

}

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.
}
// 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.

// 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.
return node;
}
```

• 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.
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.
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.

while (iter != null) {
next = iter.next.next;
copy = iter.next;
copyIter.next = copy;
copyIter = copy;
// Save the original linked list
iter.next = next;

iter = 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
// 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;
}