数据结构与算法篇（刷题篇 - 链表）
目录
1. 反转链表（简单）
1.1. 题目描述
1.2. 解题思路
方法一：迭代（推荐使用）
方法二：递归（扩展思路）
方法三：使用栈解决
方法四：双链表求解
2. 链表内指定区间反转（中等）
2.1. 题目描述
2.2. 解题思路
方法一：头插法迭代（推荐使用）
方法二：递归（扩展思路）
3. 链表中的节点每k个一组翻转（中等）
3.1. 题目描述
3.2. 解题思路
方法一：递归（推荐使用）
方法二：模拟法
4. 排序链表（中等）
4.1. 题目描述
4.2. 解题思路
方法一：自顶向下归并排序
方法二：自底向上归并排序
5. 合并两个排序的链表（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针迭代（推荐使用）
方法二：双指针递归（扩展思路）
6. 合并k个已排序的链表（较难）
6.1. 题目描述
6.2. 解题思路
方法一：归并排序思想（推荐使用）
方法二：优先队列（扩展思路）
7. 判断链表中是否有环（简单）
7.1. 题目描述
7.2. 解题思路
方法：双指针（推荐使用）
8. 链表中环的入口结点（中等）
8.1. 题目描述
8.2. 解题思路
方法：双指针（推荐使用）
9. 相交链表（简单）
9.1. 题目描述
9.2. 解题思路
方法一：哈希集合
方法二：双指针
10. 环形链表II（中等）
10.1. 题目描述
10.2. 解题思路
方法一：哈希表
方法二：快慢指针
11. 链表中倒数最后k个结点（简单）
11.1. 题目描述
11.2. 解题思路
方法一：快慢双指针（推荐使用）
方法二：先找长度再找最后k（扩展思路）
12. 两个链表的第一个公共结点（简单）
12.1. 题目描述
12.2. 解题思路
方法：双指针
13. 链表相加(二)（中等）
13.1. 题目描述
13.2 解题思路
方法：反转链表法（推荐使用）
14. 两数相加（中等）
14.1. 题目描述
14.2. 解题思路
方法一：模拟法
15. 单链表的排序（中等）
15.1. 题目描述
15.2. 解题思路
方法一：归并排序（推荐使用）
方法二：转化为数组排序（扩展思路）
16. 判断一个链表是否为回文结构（简单）
16.1. 题目描述
16.2. 解题思路
方法一：数组复制反转法（前置知识）
方法二：数组复制双指针（前置知识）
方法三：长度法找中点（推荐使用）
方法四：双指针找中点（推荐使用）
方法五：栈逆序（扩展思路）
17. 链表的奇偶重排（中等）
17.1. 题目描述
17.2. 解题思路
方法：双指针（推荐使用）
18. 删除有序链表中重复的元素-I（简单）
18.1. 题目描述
18.2. 解题思路
方法：遍历删除（推荐使用）
19. 删除有序链表中重复的元素-II（中等）
19.1. 题目描述
19.2. 解题思路
方法一：直接比较删除（推荐使用）
方法二：哈希表（扩展思路）
20. 删除链表的中间节点（中等）
20.1. 题目描述
20.2. 解题思路
方法一：快慢指针
21. 删除链表的倒数第n个节点（中等）
21.1. 题目描述
21.2. 解题思路
方法一：双指针（推荐使用）
方法二：长度统计法（思路扩展）
22. 从尾到头打印链表（简单）
22.1. 题目描述
22.2. 解题思路
23. 两两交换链表中的节点（中等）
23.1. 题目描述
23.2. 解题思路
方法一：递归
方法二：迭代
24. 复制带随机指针的链表（中等）
24.1. 题目描述
24.2. 解题思路
方法一：回溯 + 哈希表
方法二：迭代 + 节点拆分
25. 链表最大孪生和（中等）
25.1. 题目描述
25.2. 解题思路
快慢指针+ 翻转链表(头部翻转)
1. 反转链表（简单）
1.1. 题目描述
1.2. 解题思路
方法一：迭代（推荐使用）
public class Solution {public ListNode ReverseList(ListNode head) {//处理空链表if(head == null) return null;ListNode cur = head;ListNode pre = null;while(cur != null){//断开链表，要记录后续一个ListNode temp = cur.next; //当前的next指向前一个cur.next = pre; //前一个更新为当前pre = cur; //当前更新为刚刚记录的后一个cur = temp; }return pre;}
}
方法二：递归（扩展思路）
public class Solution {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;}
}
方法三：使用栈解决
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {Stack<ListNode> stack= new Stack<>();//把链表节点全部摘掉放到栈中while (head != null) {stack.push(head);head = head.next;}if (stack.isEmpty())return null;ListNode node = stack.pop();ListNode dummy = node;//栈中的结点全部出栈，然后重新连成一个新的链表while (!stack.isEmpty()) {ListNode tempNode = stack.pop();node.next = tempNode;node = node.next;}//最后一个结点就是反转前的头结点，一定要让他的next//等于空，否则会构成环node.next = null;return dummy;
}
}方法四：双链表求解
public ListNode ReverseList(ListNode head) {//新链表ListNode newHead = null;while (head != null) {//先保存访问的节点的下一个节点，保存起来//留着下一步访问的ListNode temp = head.next;//每次访问的原链表节点都会成为新链表的头结点，//其实就是把新链表挂到访问的原链表节点的//后面就行了head.next = newHead;//更新新链表newHead = head;//重新赋值，继续访问head = temp;}//返回新链表return newHead;
}2. 链表内指定区间反转（中等）
2.1. 题目描述
2.2. 解题思路
方法一：头插法迭代（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode reverseBetween (ListNode head, int m, int n) {//加个表头ListNode res = new ListNode(-1); res.next = head;//前序节点ListNode pre = res; //当前节点ListNode cur = head; //找到mfor(int i = 1; i < m; i++){ pre = cur;cur = cur.next;}//从m反转到nfor(int i = m; i < n; i++){ ListNode temp = cur.next;cur.next = temp.next;temp.next = pre.next;pre.next = temp;}//返回去掉表头return res.next; }
}
方法二：递归（扩展思路）
Java实现代码：
import java.util.*;
public class Solution {ListNode temp = null;public ListNode reverse(ListNode head, int n){//只颠倒第一个节点，后续不管if(n == 1){ temp = head.next;return head;}//进入子问题ListNode node = reverse(head.next, n - 1); //反转head.next.next = head;//每个子问题反转后的尾拼接第n个位置后的节点head.next = temp; return node;}public ListNode reverseBetween (ListNode head, int m, int n) {//从第一个节点开始if(m == 1) return reverse(head, n);//缩减子问题ListNode node = reverseBetween(head.next, m - 1, n - 1); //拼接已翻转head.next = node;return head;}
}
3. 链表中的节点每k个一组翻转（中等）
3.1. 题目描述
3.2. 解题思路
方法一：递归（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode reverseKGroup (ListNode head, int k) {//找到每次翻转的尾部ListNode tail = head;//遍历k次到尾部 for(int i = 0; i < k; i++){ //如果不足k到了链表尾，直接返回，不翻转if(tail == null) return head;tail = tail.next; }//翻转时需要的前序和当前节点ListNode pre = null; ListNode cur = head;//在到达当前段尾节点前while(cur != tail){ //翻转ListNode temp = cur.next; cur.next = pre;pre = cur;cur = temp;}//当前尾指向下一段要翻转的链表head.next = reverseKGroup(tail, k); return pre;}
}
方法二：模拟法
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode hair = new ListNode(0);hair.next = head;ListNode pre = hair;while (head != null) {ListNode tail = pre;// 查看剩余部分长度是否大于等于 kfor (int i = 0; i < k; ++i) {tail = tail.next;if (tail == null) {return hair.next;}}ListNode nex = tail.next;ListNode[] reverse = myReverse(head, tail);head = reverse[0];tail = reverse[1];// 把子链表重新接回原链表pre.next = head;tail.next = nex;pre = tail;head = tail.next;}return hair.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev = tail.next;ListNode p = head;while (prev != tail) {ListNode nex = p.next;p.next = prev;prev = p;p = nex;}return new ListNode[]{tail, head};}
}
4. 排序链表（中等）
4.1. 题目描述
4.2. 解题思路
方法一：自顶向下归并排序
class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail) {if (head == null) {return head;}if (head.next == tail) {head.next = null;return head;}ListNode slow = head, fast = head;while (fast != tail) {slow = slow.next;fast = fast.next;if (fast != tail) {fast = fast.next;}}ListNode mid = slow;ListNode list1 = sortList(head, mid);ListNode list2 = sortList(mid, tail);ListNode sorted = merge(list1, list2);return sorted;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}
方法二：自底向上归并排序
class Solution {public ListNode sortList(ListNode head) {if (head == null) {return head;}int length = 0;ListNode node = head;while (node != null) {length++;node = node.next;}ListNode dummyHead = new ListNode(0, head);for (int subLength = 1; subLength < length; subLength <<= 1) {ListNode prev = dummyHead, curr = dummyHead.next;while (curr != null) {ListNode head1 = curr;for (int i = 1; i < subLength && curr.next != null; i++) {curr = curr.next;}ListNode head2 = curr.next;curr.next = null;curr = head2;for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {curr = curr.next;}ListNode next = null;if (curr != null) {next = curr.next;curr.next = null;}ListNode merged = merge(head1, head2);prev.next = merged;while (prev.next != null) {prev = prev.next;}curr = next;}}return dummyHead.next;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead = new ListNode(0);ListNode temp = dummyHead, temp1 = head1, temp2 = head2;while (temp1 != null && temp2 != null) {if (temp1.val <= temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else if (temp2 != null) {temp.next = temp2;}return dummyHead.next;}
}
5. 合并两个排序的链表（简单）
5.1. 题目描述
5.2. 解题思路
方法一：双指针迭代（推荐使用）
Java实现代码：
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//一个已经为空了，直接返回另一个if(list1 == null) return list2;if(list2 == null)return list1;//加一个表头ListNode head = new ListNode(0); ListNode cur = head;//两个链表都要不为空while(list1 != null && list2 != null){ //取较小值的节点if(list1.val <= list2.val){ cur.next = list1;//只移动取值的指针list1 = list1.next; }else{cur.next = list2;//只移动取值的指针list2 = list2.next; }//指针后移cur = cur.next; }//哪个链表还有剩，直接连在后面if(list1 != null) cur.next = list1;elsecur.next = list2;//返回值去掉表头return head.next; }
}
方法二：双指针递归（扩展思路）
Java实现代码：
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//一个已经为空了，返回另一个if(list1 == null) return list2;if(list2 == null)return list1;//先用较小的值的节点if(list1.val <= list2.val){ //递归往下list1.next = Merge(list1.next, list2); return list1; }else{//递归往下list2.next = Merge(list1, list2.next); return list2;}}
}
6. 合并k个已排序的链表（较难）
6.1. 题目描述
6.2. 解题思路
方法一：归并排序思想（推荐使用）
图示：
Java实现代码：
import java.util.ArrayList;
public class Solution {//两个链表合并函数public ListNode Merge(ListNode list1, ListNode list2) { //一个已经为空了，直接返回另一个if(list1 == null) return list2;if(list2 == null)return list1;//加一个表头ListNode head = new ListNode(0); ListNode cur = head;//两个链表都要不为空while(list1 != null && list2 != null){ //取较小值的节点if(list1.val <= list2.val){ cur.next = list1;//只移动取值的指针list1 = list1.next; }else{cur.next = list2;//只移动取值的指针list2 = list2.next; }//指针后移cur = cur.next; }//哪个链表还有剩，直接连在后面if(list1 != null) cur.next = list1;elsecur.next = list2;//返回值去掉表头return head.next; }//划分合并区间函数ListNode divideMerge(ArrayList<ListNode> lists, int left, int right){ if(left > right) return null;//中间一个的情况else if(left == right) return lists.get(left);//从中间分成两段，再将合并好的两段合并int mid = (left + right) / 2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));}public ListNode mergeKLists(ArrayList<ListNode> lists) {//k个链表归并排序return divideMerge(lists, 0, lists.size() - 1);}
}
方法二：优先队列（扩展思路）
Java实现代码：
import java.util.*;
public class Solution {public ListNode mergeKLists(ArrayList<ListNode> lists) {//小顶堆Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val); //遍历所有链表第一个元素for(int i = 0; i < lists.size(); i++){ //不为空则加入小顶堆if(lists.get(i) != null) pq.add(lists.get(i));}//加一个表头ListNode res = new ListNode(-1); ListNode head = res;//直到小顶堆为空while(!pq.isEmpty()){ //取出最小的元素ListNode temp = pq.poll(); //连接head.next = temp; head = head.next;//每次取出链表的后一个元素加入小顶堆if(temp.next != null) pq.add(temp.next);}//去掉表头return res.next; }
}
7. 判断链表中是否有环（简单）
7.1. 题目描述
7.2. 解题思路
方法：双指针（推荐使用）
Java实现代码：
public class Solution {public boolean hasCycle(ListNode head) {//先判断链表为空的情况if(head == null) return false;//快慢双指针ListNode fast = head; ListNode slow = head;//如果没环快指针会先到链表尾while(fast != null && fast.next != null){ //快指针移动两步fast = fast.next.next; //慢指针移动一步slow = slow.next; //相遇则有环if(fast == slow) return true;}//到末尾则没有环return false; }
}
8. 链表中环的入口结点（中等）
8.1. 题目描述
8.2. 解题思路
方法：双指针（推荐使用）
Java实现代码：
public class Solution {//判断有没有环，返回相遇的地方public ListNode hasCycle(ListNode head) {//先判断链表为空的情况if(head == null) return null;//快慢双指针ListNode fast = head; ListNode slow = head;//如果没环快指针会先到链表尾while(fast != null && fast.next != null){ //快指针移动两步fast = fast.next.next; //慢指针移动一步slow = slow.next; //相遇则有环，返回相遇的位置if(fast == slow) return slow;}//到末尾说明没有环，返回nullreturn null; }public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode slow = hasCycle(pHead);//没有环if(slow == null) return null;//快指针回到表头ListNode fast = pHead; //再次相遇即是环入口while(fast != slow){ fast = fast.next;slow = slow.next;}return slow;}
}
9. 相交链表（简单）
9.1. 题目描述
9.2. 解题思路
方法一：哈希集合
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}
方法二：双指针
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}
10. 环形链表II（中等）
10.1. 题目描述
10.2. 解题思路
方法一：哈希表
public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos = head;Set<ListNode> visited = new HashSet<ListNode>();while (pos != null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos = pos.next;}return null;}
}
方法二：快慢指针
public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode slow = head, fast = head;while (fast != null) {slow = slow.next;if (fast.next != null) {fast = fast.next.next;} else {return null;}if (fast == slow) {ListNode ptr = head;while (ptr != slow) {ptr = ptr.next;slow = slow.next;}return ptr;}}return null;}
}
11. 链表中倒数最后k个结点（简单）
11.1. 题目描述
11.2. 解题思路
方法一：快慢双指针（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode FindKthToTail (ListNode pHead, int k) {int n = 0;ListNode fast = pHead; ListNode slow = pHead;//快指针先行k步for(int i = 0; i < k; i++){ if(fast != null)fast = fast.next;//达不到k步说明链表过短，没有倒数kelse return slow = null;}//快慢指针同步，快指针先到底，慢指针指向倒数第k个while(fast != null){ fast = fast.next;slow = slow.next;}return slow;}
}
方法二：先找长度再找最后k（扩展思路）
Java实现代码：
import java.util.*;
public class Solution {public ListNode FindKthToTail (ListNode pHead, int k) {int n = 0;ListNode p = pHead;//遍历链表，统计链表长度while(p != null){n++;p = p.next;}//长度过小，返回空链表if(n < k) return null;p = pHead;//遍历n-k次for(int i = 0; i < n - k; i++) p = p.next;return p;}
}
12. 两个链表的第一个公共结点（简单）
12.1. 题目描述
12.2. 解题思路
方法：双指针
Java实现代码：
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode l1 = pHead1, l2 = pHead2;while(l1 != l2){l1 = (l1==null)?pHead2:l1.next;l2 = (l2==null)?pHead1:l2.next;}return l1;}
}
13. 链表相加(二)（中等）
13.1. 题目描述
13.2 解题思路
方法：反转链表法（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {//反转链表public ListNode ReverseList(ListNode pHead) { if(pHead == null)return null;ListNode cur = pHead;ListNode pre = null;while(cur != null){//断开链表，要记录后续一个ListNode temp = cur.next;//当前的next指向前一个cur.next = pre; //前一个更新为当前pre = cur; //当前更新为刚刚记录的后一个cur = temp; }return pre;}public ListNode addInList (ListNode head1, ListNode head2) {//任意一个链表为空，返回另一个if(head1 == null) return head2;if(head2 == null)return head1;//反转两个链表head1 = ReverseList(head1); head2 = ReverseList(head2);//添加表头ListNode res = new ListNode(-1); ListNode head = res;//进位符号int carry = 0; //只要某个链表还有或者进位还有while(head1 != null || head2 != null || carry != 0){ //链表不为空则取其值int val1 = head1 == null ? 0 : head1.val; int val2 = head2 == null ? 0 : head2.val;//相加int temp = val1 + val2 + carry; //获取进位carry = temp / 10; temp %= 10; //添加元素head.next = new ListNode(temp); head = head.next;//移动下一个if(head1 != null) head1 = head1.next;if(head2 != null)head2 = head2.next;}//结果反转回来return ReverseList(res.next); }
}
14. 两数相加（中等）
14.1. 题目描述
14.2. 解题思路
方法一：模拟法
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;}
}
15. 单链表的排序（中等）
15.1. 题目描述
15.2. 解题思路
方法一：归并排序（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {//合并两段有序链表ListNode merge(ListNode pHead1, ListNode pHead2) { //一个已经为空了，直接返回另一个if(pHead1 == null) return pHead2;if(pHead2 == null)return pHead1;//加一个表头ListNode head = new ListNode(0); ListNode cur = head;//两个链表都要不为空while(pHead1 != null && pHead2 != null){ //取较小值的节点if(pHead1.val <= pHead2.val){ cur.next = pHead1;//只移动取值的指针pHead1 = pHead1.next; }else{cur.next = pHead2;//只移动取值的指针pHead2 = pHead2.next; }//指针后移cur = cur.next; }//哪个链表还有剩，直接连在后面if(pHead1 != null) cur.next = pHead1;elsecur.next = pHead2;//返回值去掉表头return head.next; }public ListNode sortInList (ListNode head) {//链表为空或者只有一个元素，直接就是有序的if(head == null || head.next == null) return head;ListNode left = head; ListNode mid = head.next;ListNode right = head.next.next;//右边的指针到达末尾时，中间的指针指向该段链表的中间while(right != null && right.next != null){ left = left.next;mid = mid.next;right = right.next.next;}//左边指针指向左段的左右一个节点，从这里断开left.next = null; //分成两段排序，合并排好序的两段return merge(sortInList(head), sortInList(mid)); }
}
方法二：转化为数组排序（扩展思路）
import java.util.*;
public class Solution {public ListNode sortInList (ListNode head) {ArrayList<Integer> nums = new ArrayList(); ListNode p = head;//遍历链表，将节点值加入数组while(p != null){ nums.add(p.val);p = p.next;}p = head;//对数组元素排序Collections.sort(nums); //遍历数组for(int i = 0; i < nums.size(); i++){ //将数组元素依次加入链表p.val = nums.get(i); p = p.next;}return head;}
}
16. 判断一个链表是否为回文结构（简单）
16.1. 题目描述
16.2. 解题思路
方法一：数组复制反转法（前置知识）
Java实现代码：
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ArrayList<Integer> nums = new ArrayList();//将链表元素取出一次放入数组while(head != null){ nums.add(head.val);head = head.next;}ArrayList<Integer> temp = new ArrayList();temp = (ArrayList<Integer>) nums.clone();//准备一个数组承接翻转之后的数组Collections.reverse(temp); for(int i = 0; i < nums.size(); i++){int x = nums.get(i);int y = temp.get(i);//正向遍历与反向遍历相同if(x != y) return false;}return true;}
}
方法二：数组复制双指针（前置知识）
Java实现代码：
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ArrayList<Integer> nums = new ArrayList();//将链表元素取出一次放入数组while(head != null){ nums.add(head.val);head = head.next;}//双指针指向首尾int left = 0; int right = nums.size() - 1;//分别从首尾遍历，代表正序和逆序while(left <= right){ int x = nums.get(left);int y = nums.get(right);//如果不一致就是不为回文if(x != y) return false;left++;right--;}return true;}
}
方法三：长度法找中点（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {//反转链表指针ListNode reverse(ListNode head) { //前序节点ListNode prev = null; while(head != null){//断开后序ListNode next = head.next; //指向前序head.next = prev; prev = head;head = next;}return prev;}public boolean isPail (ListNode head) {ListNode p = head;int n = 0;//找到链表长度while(p != null){ n++;p = p.next; }//中点n = n / 2; p = head;//遍历到中点位置while(n > 0){ p = p.next;n--;}//中点处反转p = reverse(p); ListNode q = head;while(p != null){//比较判断节点值是否相等if(p.val != q.val) return false;p = p.next;q = q.next;}return true;}
}
方法四：双指针找中点（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {//反转链表指针ListNode reverse(ListNode head) { //前序节点ListNode prev = null; while(head != null){//断开后序ListNode next = head.next; //指向前序head.next = prev; prev = head;head = next;}return prev;}public boolean isPail (ListNode head) {//空链表直接为回文if(head == null) return true;//准备快慢双指针ListNode slow = head; ListNode fast = head;//双指针找中点while(fast != null && fast.next != null){ slow = slow.next;fast = fast.next.next;}//中点处反转slow = reverse(slow); fast = head;while(slow != null){ //比较判断节点值是否相等if(slow.val != fast.val) return false;fast = fast.next;slow = slow.next;}return true;}
}
方法五：栈逆序（扩展思路）
Java实现代码：
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ListNode p = head;Stack<Integer> s = new Stack();//辅助栈记录元素while(p != null){ s.push(p.val);p = p.next;}p = head;//正序遍历链表，从栈中弹出的内容是逆序的while(!s.isEmpty()){ //比较是否相同if(p.val != s.pop()) return false;p = p.next;}return true;}
}
17. 链表的奇偶重排（中等）
17.1. 题目描述
17.2. 解题思路
方法：双指针（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode oddEvenList (ListNode head) {//如果链表为空，不用重排if(head == null) return head;//even开头指向第二个节点，可能为空ListNode even = head.next; //odd开头指向第一个节点ListNode odd = head; //指向even开头ListNode evenhead = even; while(even != null && even.next != null){//odd连接even的后一个，即奇数位odd.next = even.next; //odd进入后一个奇数位odd = odd.next; //even连接后一个奇数的后一位，即偶数位even.next = odd.next; //even进入后一个偶数位even = even.next; } //even整体接在odd后面odd.next = evenhead; return head;}
}
18. 删除有序链表中重复的元素-I（简单）
18.1. 题目描述
18.2. 解题思路
方法：遍历删除（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head == null) return null;//遍历指针ListNode cur = head; //指针当前和下一位不为空while(cur != null && cur.next != null){ //如果当前与下一位相等则忽略下一位if(cur.val == cur.next.val) cur.next = cur.next.next;//否则指针正常遍历else cur = cur.next;}return head;}
}
19. 删除有序链表中重复的元素-II（中等）
19.1. 题目描述
19.2. 解题思路
方法一：直接比较删除（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head == null) return null;ListNode res = new ListNode(0);//在链表前加一个表头res.next = head; ListNode cur = res;while(cur.next != null && cur.next.next != null){ //遇到相邻两个节点值相同if(cur.next.val == cur.next.next.val){ int temp = cur.next.val;//将所有相同的都跳过while (cur.next != null && cur.next.val == temp) cur.next = cur.next.next;}else cur = cur.next;}//返回时去掉表头return res.next; }
}
方法二：哈希表（扩展思路）
Java实现代码：
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head == null) return null;Map<Integer,Integer> mp = new HashMap<>();ListNode cur = head;//遍历链表统计每个节点值出现的次数while(cur != null){ if(mp.containsKey(cur.val))mp.put(cur.val, (int)mp.get(cur.val) + 1);elsemp.put(cur.val,1);cur = cur.next;}ListNode res = new ListNode(0);//在链表前加一个表头res.next = head; cur = res;//再次遍历链表while(cur.next != null){//如果节点值计数不为1 if(mp.get(cur.next.val) != 1) //删去该节点cur.next = cur.next.next; elsecur = cur.next; }//去掉表头return res.next; }
}
20. 删除链表的中间节点（中等）
20.1. 题目描述
20.2. 解题思路
解题思路： 使用 slow 记录慢指针，fast 记录快指针。
当 fast 的再一次移动就结束时，说明 slow 的再一次移动也将到达中间点，
那么这个时候就可以直接用 slow.next = slow.next.next 来去掉中间节点。
方法一：快慢指针
class Solution {public ListNode deleteMiddle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head;ListNode fast = head.next;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}slow.next = slow.next.next;return head;}
}21. 删除链表的倒数第n个节点（中等）
21.1. 题目描述
21.2. 解题思路
方法一：双指针（推荐使用）
Java实现代码：
import java.util.*;
public class Solution {public ListNode removeNthFromEnd (ListNode head, int n) {//添加表头ListNode res = new ListNode(-1); res.next = head;//当前节点ListNode cur = head; //前序节点ListNode pre = res; ListNode fast = head;//快指针先行n步while(n != 0){ fast = fast.next;n--;}//快慢指针同步，快指针到达末尾，慢指针就到了倒数第n个位置while(fast != null){fast = fast.next;pre = cur;cur = cur.next;}//删除该位置的节点pre.next = cur.next; //返回去掉头return res.next; }
}
方法二：长度统计法（思路扩展）
Java实现代码：
import java.util.*;
public class Solution {public ListNode removeNthFromEnd (ListNode head, int n) {//记录链表长度int length = 0; //添加表头ListNode res = new ListNode(-1); res.next = head;//当前节点ListNode cur = head; //前序节点ListNode pre = res; //找到链表长度while(cur != null){ length++;cur = cur.next;}//回到头部cur = head; //从头遍历找到倒数第n个位置for(int i = 0; i < length - n; i++){ pre = cur;cur = cur.next;}//删去倒数第n个节点pre.next = cur.next; //返回去掉头节点return res.next; }
}
22. 从尾到头打印链表（简单）
22.1. 题目描述
22.2. 解题思路
class Solution {public int[] reversePrint(ListNode head) {int count = 0; //链表结点的个数ListNode p = head;while(p != null){ //统计链表中结点的个数count++;p = p.next;}int[] ans = new int[count]; //创建一个和结点个数等大的数组p = head;int index = count - 1; //作为索引填充数组（从后往前填充）while(p != null){ans[index] = p.val;p = p.next;index--;}return ans;}
}23. 两两交换链表中的节点（中等）
23.1. 题目描述
23.2. 解题思路
方法一：递归
class Solution {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;}
}
方法二：迭代
Java代码：
class Solution {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;}
}
24. 复制带随机指针的链表（中等）
24.1. 题目描述
24.2. 解题思路
方法一：回溯 + 哈希表
Java代码：
class Solution {Map<Node, Node> cachedNode = new HashMap<Node, Node>();public Node copyRandomList(Node head) {if (head == null) {return null;}if (!cachedNode.containsKey(head)) {Node headNew = new Node(head.val);cachedNode.put(head, headNew);headNew.next = copyRandomList(head.next);headNew.random = copyRandomList(head.random);}return cachedNode.get(head);}
}
方法二：迭代 + 节点拆分
class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}for (Node node = head; node != null; node = node.next.next) {Node nodeNew = new Node(node.val);nodeNew.next = node.next;node.next = nodeNew;}for (Node node = head; node != null; node = node.next.next) {Node nodeNew = node.next;nodeNew.random = (node.random != null) ? node.random.next : null;}Node headNew = head.next;for (Node node = head; node != null; node = node.next) {Node nodeNew = node.next;node.next = node.next.next;nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;}return headNew;}
}
25. 链表最大孪生和（中等）
25.1. 题目描述
25.2. 解题思路
快慢指针+ 翻转链表(头部翻转)
传统方法：
- 先使用快慢指针找到中间节点 Using the Fast& Slow pointers to Find the middle point
- 翻转第二部分 Reverse the secondPart
- 通过同时遍历第一部分与反转后的第二部分得出最大结果 Add the values and store the maximum value
具体代码如下：
class Solution {public int pairSum(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode prev = reverse(slow);ListNode head1 = head, head2 = prev;int res = 0;while (head2 != null) {res = Math.max(head1.val + head2.val, res);head1 = head1.next;head2 = head2.next;}return res;}private ListNode reverse(ListNode head) {if (head == null || head.next == null) {return head;}ListNode curr = head;ListNode prev = null;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}对原有思路进行改进：
可以在使用快慢指针时同时对第一部分（前一半）链表进行翻转操作 相较于原先 找到中间节点后翻转第二部分 更加简洁快速
具体代码如下：
class Solution {public int pairSum(ListNode head) {ListNode fast = head;ListNode slow = head;ListNode prev = null;while (fast != null && fast.next != null) {fast = fast.next.next;ListNode next = slow.next;slow.next = prev;prev = slow;slow = next;}int res = 0;while (slow != null) {res = Math.max(res, prev.val + slow.val);prv = prev.next;slow = slow.next;}return res;}}相关文章：
数据结构与算法篇（刷题篇 - 链表）
目录 1. 反转链表（简单） 1.1. 题目描述 1.2. 解题思路 方法一：迭代（推荐使用） 方法二：递归（扩展思路） 方法三：使用栈解决 方法四：双链表求解 2. 链表内…...
TinyAgent: 从零开始构建最小化Agent系统
引言 随着大模型（LLM）的崛起，特别是ChatGPT等大模型的广泛应用，基于LLM的系统越来越受欢迎。然而，尽管大模型具备强大的生成能力和推理能力，它们在处理某些专有领域或实时问题时仍然存在局限性。因此&#…...
Android Studio New里面没有New Flutter Project
跟着Flutter中文网的配置教程，安装好了flutter,在Android studio里面也安装了dart和flutter的插件。重启后还是在FIle->New里面没有显示New Flutter Project。 反复卸载重装dart和flutter插件好几次，依然没有效果。 原来是没有把Android APK Suppor…...
linux信号 | 学习信号四步走 | 透析信号是如何被处理的？
前言：本节内容讲述linux信号的捕捉。 我们通过前面的学习， 已经学习了信号的概念， 信号的产生， 信号的保存。 只剩下信号的处理。 而信号的处理我们应该着重注意的是第三种处理方式——信号的捕捉。 也就是说， 这篇文章…...
mysql语句执行过程
具体流程如下: 1】当客户端的SOL发送到MySQL时，首先是到达服务器层的连接器，连接器会对你此次发起的连接进行权限校验，以此来获取你这个账号拥有的权限。当你的账号或密码不正确时，会报用户错误。连接成功如果后续没有任何操作&am…...
最新版本SkyWalking【10.1.0】部署
这里写目录标题 前言前置条件启动Skywalking下载解压启动说明 集成Skywalking Agent下载Agent在IDEA中添加agent启动应用并访问SpringBoot接口 说明 前言 基于当前最新版10.1.0搭建skywalking 前置条件 装有JDK11版本的环境了解SpringBoot相关知识 启动Skywalking 下载 地…...
WSL2 中配置桥接模式、虚拟交换机及固定 IP
WSL2 中配置桥接模式、虚拟交换机及固定 IP 一、创建虚拟交换机1.1 使用 Hyper-V 管理器创建虚拟交换机1.2 使用 PowerShell 创建虚拟交换机 二、更新 WSL 配置三、设置 WSL2 中的静态 IP、网关和 DNS3.1 编辑网络配置文件3.2 应用网络配置3.3 测试网络连接 四、重启 WSL 在使用…...
Unite Shanghai 2024 团结引擎专场 | 团结引擎 OpenHarmony 工程剖析
在 2024 年 7 月 24 日的 Unite Shanghai 2024 团结引擎专场演讲中，Unity中国 OpenHarmony 技术负责人刘伟贤对团结引擎导出的 OpenHarmony 工程进行了细节剖析，详细讲解 XComponent 如何与引擎结合，UI 线程和引擎线程的关联以及 ts/ets 的代…...
计算机毕业设计 基于Hadoop的智慧校园数据共享平台的设计与实现 Python毕业设计 Python毕业设计选题 Spark 大数据【附源码+安装调试】
博主介绍：✌从事软件开发10年之余，专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...
2022CCPC绵阳站VP题解报告(CGHMAE六题)
文章目录 2022CCPC绵阳站VP题解报告前言[Problem - C ](https://codeforces.com/gym/104065/problem/C) （签到思维）[H (codeforces.com)](https://codeforces.com/gym/104065/problem/H) （签到构造）[Problem - G ](https://codefo…...
代码随想录day23：贪心part1
455. 分发饼干 class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int res 0;int index s.length - 1;for(int i g.length - 1; i > 0; i--){if(index > 0 && s[index] > g[i]){res;index--;}}return r…...
通过网页设置参数，submit还是json
在通过网页设置参数并发送到服务器时，选择使用submit（通常是通过HTML表单的提交）还是直接发送JSON数据（通常是通过AJAX请求，如使用fetch API）取决于几个因素，包括你的服务器端如何处理这些请求、…...
C语言 | Leetcode C语言题解之第463题岛屿的周长
题目： 题解： const int dx[4] {0, 1, 0, -1}; const int dy[4] {1, 0, -1, 0};int dfs(int x, int y, int** grid, int n, int m) {if (x < 0 || x > n || y < 0 || y > m || grid[x][y] 0) {return 1;}if (grid[x][y] 2) {return 0;}g…...
逼近理论及应用精解【12】
文章目录 卷积卷积层与滤波层定义数学原理与公式定理架构例子例题 卷积层和滤波层概念的详细解释卷积层滤波层 滤波层和卷积层在卷积神经网络（CNN）中区别滤波层卷积层总结卷积层的数学原理滤波层的数学原理 参考文献 卷积 卷积层与滤波层 定义 卷积层…...
LIN总线学习大全（基于CANoe和CAPL）
🍅 我是蚂蚁小兵，专注于车载诊断领域，尤其擅长于对CANoe工具的使用🍅 寻找组织 ，答疑解惑，摸鱼聊天，博客源码，点击加入👉【相亲相爱一家人】🍅 玩转CANoe&…...
国庆作业
day1 1.开发环境 Linux系统GCCFDBmakefilesqlite3 2.功能描述 项目功能: 服务器：处理客户端的请求，并将数据存入数据库中，客户端请求的数据从数据库进行获取，服务器转发给客户端。 用户客户端：实现账号的注册、登…...
Android OpenGLES2.0开发（四）：矩阵变换和相机投影
事物的本质是事物本身所固有的、深藏于现象背后并决定或支配现象的方面。 还记得我们上一篇绘制的三角形吗，我们确实能够顺利用OpenGL ES绘制出图形了，这是一个好的开始，但这还远远不够。我们定义的坐标是正三角形，但是绘制出…...
快递查询软件：实现单号识别与批量物流查询的高效工具
随着网络购物的普及，快递物流行业迎来了前所未有的发展机遇，同时也面临着巨大的挑战。跟踪物流信息成为一个难题，因此，快递查询软件的核心功能之一便是单号识别。传统的快递单号输入方式繁琐且易出错在此背景下，快递查…...
nodejs与npm版本对应表
Node.js — Node.js 版本 (nodejs.org)...
Spring Boot 项目中如何使用异步任务
前置知识： 同步任务： 同步任务是在单线程中按顺序执行，每次只有一个任务在执行，不会引发线程安全和数据一致性等并发问题 同步任务需要等待任务执行完成后才能执行下一个任务，无法同时处理多个任务，响应慢…...
Scrum实战中遇到的问题与解决方法
在当今快速变化的技术环境中，IT企业面临着持续的市场压力和竞争，传统的瀑布式开发模式已经难以满足现代企业的需要。瀑布模型过于僵化，缺乏灵活性，导致项目经常延期，成本增加，最终可能无法达到预期效果。为…...
全面介绍 Windows 录屏工具：开启录制新篇章
高质量的录屏工具是我们录屏的得力助手。但是日常因为侧重点的不同，比如有的喜欢录制游戏画面、有的需要录制教学视频、演示操作也需要录屏工具。这次我们就来探讨一下windows录屏工具有哪些吧。 1.福晰录屏大师 链接：www.foxitsoftware.cn/REC/ 从这…...
Maven 和 NetBeans：集成与使用
Maven 和 NetBeans：集成与使用 Maven 和 NetBeans 是两款强大的工具，常用于Java开发。Maven是一个项目管理工具，它能够帮助管理项目的构建、报告和文档。NetBeans是一个集成开发环境（IDE），它为Java开发提供了丰富的功能和友好的用户界面。将Maven集成到NetBeans中，可以…...
【系统架构设计师】目录提纲
一、绪论（TODO） 二、计算机与网络基础知识（TODO） 三、信息系统基础知识（TODO） 四、系统开发基础知识（TODO） 五、软件架构设计（TODO） 六、UML建模与架构文…...
【微服务】—SpringBoot入门
⭐⭐⭐⭐⭐⭐ Github主页👉https://github.com/A-BigTree 笔记仓库👉https://github.com/A-BigTree/tree-learning-notes 个人主页👉https://www.abigtree.top ⭐⭐⭐⭐⭐⭐ 文章目录 1 SpringBoot快速入门1.1 SpringBoot简介1.1.1 简介1.1.2…...
Linux: debug: perf: report: --sort
文章目录 简介实例简介 接上回：https://mzhan017.blog.csdn.net/article/details/142689870。 这里介绍perf的这个参数，还是非常的有用，尤其是分析对整个系统做perf record的数据，而不是单个进程做perf record。-s, --sort= ： Sort histogram entries by given key(s) - …...
like 模糊查询的底层算法
like 模糊查询的底层算法 全文搜索算法、模糊查询、n-gram分隔算法功能介绍 百度搜索，文心一言给出的结果： SQL模糊查询底层通常使用全文搜索算法，如LIKE操作符和全文索引通常使用的n-gram分割算法。 n-gram是一种将文本分割成固定大小的词…...
【Linux实践】实验九：Shell流程控制语句
文章目录 实验九：Shell流程控制语句实验目的：实验内容：操作步骤：1. 复制*.c文件并排序2. 计算1-10的平方 实验九：Shell流程控制语句 实验目的： 掌握条件判断语句，如if语句、case语句。掌握循环…...
YOLOv8实战TT100K中国交通标志检测【数据集+YOLOv8模型+源码+PyQt5界面】
YOLOv8实战TT100k交通标志识别 文章目录 研究背景资源获取1.前言1.1 YOLO 系列：中国交通标志检测领域的璀璨明星1.2 Transformer与注意力机制：为中国交通标志检测注入新活力1.3 中国交通标志检测技术：迎接挑战，砥砺前行1.4 YOLOv8…...
SQLite3
文章目录 SQLite3 C/CAPI介绍SQLite3 C/C API 使⽤ SQLite3 C/CAPI介绍 C/C API是SQLite3数据库的⼀个客⼾端，提供⼀种⽤C/C操作数据库的⽅法。 SQLite3 C/C API 使⽤ 下⾯我们将这⼏个接⼝封装成⼀个类，快速上⼿这⼏个接口 创建/打开数据库文件针对打开…...