Leetcode-cn.com/problems/re…

``````class Solution {
ListNode pre = null;
while(cur ! =null){
ListNode help = cur.next;
// pre cur help
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code``````

## 2. A group of k reverse singly linked lists

Leetcode-cn.com/problems/re…

``````class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
for(int i = 0 ; i < k ; i++){
cur = cur.next;
}

}

ListNode reverse(ListNode head , ListNode end){
ListNode pre = null;
while(cur ! = end){ ListNode help = cur.next;//pre cur help
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code``````

## 3. Reverse left to right singly linked list

Leetcode-cn.com/problems/re…

``````
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
//2. Find the m-1 node that started the flip and save it with cur
ListNode cur = dummy;
for(int i = 1; i < m ; i++) cur = cur.next; // start from dummy node

// a is the MTH node
ListNode a = cur.next;
ListNode tail = cur.next; // Use tail to store this node. After flipping the tail, attach it to the previous list

//4. Flip the single linked list
ListNode pre = null;
ListNode help = null;
for(inti = m ; i <= n ; i++){ help = a.next; a.next = pre; pre = a; a = help; }//5. After flipping, pre is the head node, tail is the tail node, and help is the next node of the tail node.
cur.next = pre;
tail.next = help;
returndummy.next; }}Copy the code``````

## 4. Swap linked list nodes in pairs

Leetcode-cn.com/problems/sw…

``````class Solution {
//1. Verify data
ListNode dummy = new ListNode(0);

//3. Start flipping
ListNode cur = dummy;
// The last two nodes are not null because there are still two nodes that can be swapped
while(cur.next ! =null&& cur.next.next ! =null) {// Define two pointer locations
ListNode a = cur.next;
ListNode b = cur.next.next;
// Start the exchange
// cur a b
ListNode c = b.next;

cur.next = b;
b.next = a;
a.next = c;
cur = a;
}
returndummy.next; }}Copy the code``````

## 5. Determine if it’s a palindrome list

Leetcode-cn.com/problems/pa…

``````class Solution {
// Find the midpoint of the fast and slow pointer
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}

/ / missile for midpoint
ListNode a = slow.next;
slow.next = null;

cur =cur.next;
}
return true;

}

ListNode pre = null;
while(cur ! =null){
ListNode help = cur.next;
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code``````

Leetcode-cn.com/problems/re…

``````class Solution {
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
ListNode a = reverse(slow.next);
slow.next = null;
while(a ! =null&& b ! =null){
ListNode c = a.next;
ListNode d = b.next;
//a c
//b db.next = a; a.next = d; a = c; b = d; }}ListNode reverse(ListNode head){
ListNode pre = null;
while(cur ! =null){
ListNode help = cur.next;
cur.next = pre;
pre = cur;
cur = help;
}
returnpre; }}Copy the code``````

Leetcode-cn.com/problems/od…

``````class Solution {

while(b ! =null&& b.next ! =null){
ListNode c = b.next;
ListNode d = c.next;
//a b c d
a.next = c;
b.next = d;
a = a.next;
b = b.next;
}

## 8. The first common node of both lists

Leetcode-cn.com/problems/li…

``````public class Solution {
while(l1 ! = l2){ l1 = l1 ==null ? headB : l1.next;
l2 = l2 == null ? headA : l2.next;
}
returnl1; }}Copy the code``````

## 9. Rotate the list

Leetcode-cn.com/problems/ro…

``````class Solution {
public ListNode rotateRight(ListNode head, int k) {
//1. Find the length of the list
int len = 1;
while(cur.next ! =null){
cur = cur.next;
len++;
}

//2. End to end, find x
k = k % len;
int x = len - k;
//3. Find the x node, which is the header to return
while(x > 0){
cur = cur.next;
x--;
}
ListNode res = cur.next;
cur.next = null;
returnres; }}Copy the code``````

## 5. Merge two sorted singly linked lists

Leetcode-cn.com/problems/me…

``````class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1. Verify data
if(l1 == null || l2 == null) return  l1 == null ? l2 : l1;
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//3. The two Pointers move backwards. The node is small enough to end with a cur
while(l1 ! =null&& l2 ! =null) {if(l1.val < l2.val){
cur.next = new ListNode(l1.val);
cur = cur.next; //cur also moves back one
l1 = l1.next;
}else{
cur.next = newListNode(l2.val); cur = cur.next; l2 = l2.next; }}//4. The rest of the linked list can be directly connected, because it is already sorted
cur.next = l1 == null ? l2 : l1;
returndummy.next; }}Copy the code``````

## 6. Merge k sorted single linked lists

Leetcode-cn.com/problems/me…

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//1. Create a small root heap
Queue<ListNode> heap = new PriorityQueue<>((a , b) -> (a.val - b.val));
//2. Place all headers in the heap, so that the top of the heap is the smallest
for(ListNode node : lists){
}
// create a virtual node
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//4. Keep popping the top node after cur and push the next node of the popping node into the heap again
while(! heap.isEmpty()){ ListNode minNode = heap.poll(); cur.next = minNode; cur = cur.next;if(minNode.next ! =null) heap.add(minNode.next);
}
returndummy.next; }}Copy the code``````

Leetcode-cn.com/problems/pa…

``````class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(-1);
ListNode a = dummy1;
ListNode dummy2 = new ListNode(-1);
ListNode b = dummy2;
while(cur ! =null) {if(cur.val < x){
a.next = cur;
cur = cur.next;
a = a.next;
}else{
b.next = cur;
cur = cur.next;
b = b.next;
}
}

a.next = dummy2.next;
b.next = null;
returndummy1.next; }}Copy the code``````

# The fast or slow pointer finds the NTH node from the bottom

## 1. Delete the penultimate node of the linked list

Leetcode-cn.com/problems/re…

``````class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
ListNode fast = dummy;
ListNode slow = dummy;
while(n > 0){
fast = fast.next;
n--;
}

while(fast.next ! =null){
fast = fast.next;
slow = slow.next;
}

slow.next = slow.next.next;
returndummy.next; }}Copy the code``````

## 2. Find the middle node of the list – if there are two middle nodes, return the second middle node

Leetcode-cn.com/problems/mi…

``````
class Solution {
If there are two intermediate nodes, return the second intermediate node.
while(fast ! =null&& fast.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
returnslow; }}Copy the code``````

# List order

## 1. List merge sort

Leetcode-cn.com/problems/so…

``````class Solution {
}

//1. Recursive termination condition
//2
while(fast.next ! =null&& fast.next.next ! =null){
fast = fast.next.next;
slow = slow.next;
}
//3
ListNode r = mergeSort(slow.next);
slow.next = null;
//4. Sort recursively on the left
//5. Merge two lists
return merge(l,r);
}

ListNode merge(ListNode l , ListNode r){
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l ! =null&& r ! =null) {if(l.val <= r.val){
cur.next = l;
l = l.next;
cur = cur.next;
}else{
cur.next = r;
r = r.next;
cur = cur.next;
}
}

cur.next = l == null ? r : l;
returndummy.next; }}Copy the code``````

# Removes duplicate elements from the linked list

## 1. Delete only one duplicate element

Leetcode-cn.com/problems/re…

``````class Solution {

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

## 2. Delete all duplicate elements

Leetcode-cn.com/problems/re…

``````
class Solution {