LeetCode Hot100刷题指南(第3期)
大家好 我是寸铁
临近秋招，让我们一起刷题吧
每期5道题 持续更新中:running:
欢迎点赞 + 关注 
往期回顾
蓝桥杯上岸全指南
LeetCode Hot100刷题指南(第一期)
LeetCode Hot100刷题指南(第二期)
操作系统期末题库 第九期(完结）
数据库SQL语句（期末冲刺不挂科）
暑假完善蓝桥杯和Leetcode系列，欢迎各位同学前来交流 
第三期
141. 环形链表
类似题目
类似：234. 回文链表
解题思路
快慢指针，如果链表存在有环，快指针fast 一定会追上慢指针slow。
因为当 fast 从后面接近slow时, 有两种可能性:
1. fast 比 slow 慢一步
2. fast 比 slow 慢两步
3. 快指针与慢指针之间差n步
所以:
1. fast 比 slow 慢一步: fast 走了两步, slow 走了一步, fast 与 slow 相遇
2. fast 比 slow 慢两步: fast 走了两步, slow 走了一步, fast 与 slow 相差1步, 回到第一种情况
3. 此时继续往后走，slow前进一步，fast前进两步，两者之间相差n+1-2即n-1步。重复这个过程，直到快指针和慢指针相遇。
所以, 如果链表有环, 快指针一定会追上慢指针, 二者相遇。
通常设定快指针比慢指针多走一步，减少访问链表的频率。
注意
slow 和 fast 最初设定不能都等于head
这道题不同于234. 回文链表
234. 回文链表是去找到链表的中点
这道题是去看有无环，用快慢指针做，最终两指针相遇。
while循环的终止条件为slow != fast
如果一开始slow = head; fast = head;
则循环不进行，与目的不符合。
证明推导
时间复杂度
最多遍历一遍链表的n个节点
总计为O(n)
代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//当无节点或者只有一个节点
if(head == null || head.next == null){
return false;
}
//定义起点位置，相当于同一起跑线，不影响后面的步数之差
//2个节点以上，包含环,用快慢指针
ListNode slow = head;
ListNode fast = head.next;
//还没有相遇时
while(slow != fast){
//快指针跑得比慢指针快，先让他去判断
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;//走一步
fast = fast.next.next;//走两步
}
return true;
}
}
21. 合并两个有序链表
解题思路
先判断为空链表的情况(递归的基值)
1. l1为空链表则返回l2
2. l2为空链表则返回l1
再进行合并
合并根据两链表节点值的大小进行合并
1. l1的值 < l2的值 则l1的下一个节点指向l2
2. l1的值 >= l2的值 则l2的下一个节点指向l1
每次更新后，将当前的链表进行返回，用于下一次递归合并两链表
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//l1为空链表则返回l2
if(l1 == null){
return l2;
}
//l2为空链表则返回l1
else if(l2 == null){
return l1;
}
//比较两链表的数值
//l1的值 < l2的值 则l1的下一个节点指向l2
else if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next , l2);
return l1;
}
//l1的值 >= l2的值 则l2的下一个节点指向l1
else{//l1.val >= l2.val
l2.next = mergeTwoLists(l2.next , l1);
return l2;
}
}
}
19. 删除链表的倒数第 N 个结点
思路
删除倒数第n个节点
做法1
- 直接枚举，从前往后先枚举，找到要删除节点的前一个节点。
再让该节点的next指针指向下一个节点即可。 - 枚举的次数与长度
len、倒数第n个有关
这里为统一删第n个，枚举时从1开始。 - 存在关系：
len - n + 1(+1 是因为下标从1开始 )
注意：出现删除头节点的情况时。
原有的头节点需要更新，直接删除头节点不好删。
这时我们需要借助哑节点hummy，hummy的next指向head。
需要删除head时让hummy的next指向head.next即可。
Accode
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode nummy = new ListNode(0 , head);//存储值为0、next指向head;
ListNode cur = nummy;
int len = getLength(head);
for(int i = 1; i < len - n + 1; i++){
cur = cur.next;
}
//从0开始
<!--
for(int i = 0; i < len - n ; i++){
cur = cur.next;
}
-->
cur.next = cur.next.next;
ListNode ans = nummy.next;
return ans;
}
public int getLength(ListNode head){
int len = 0;
while(head != null){
head = head.next;
len++;
}
return len;
}
}
时间复杂度
最多遍历整个链表一遍
总计为O(n)
做法2
- 运用栈的结构，先进后出。
- 要删的是倒数第
n个节点，可以popn次 - 再访问当前栈中的栈顶(倒数第n个节点的前驱节点)，让该栈顶的
next指向该栈顶的next的next。 - 这样可以将pop出来的第n个元素给删掉
ACcode
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0 , head);
Deque <ListNode> stack = new LinkedList<ListNode>();//创建一个栈，栈存ListNode
ListNode cur = dummy;
while(cur != null){
stack.push(cur);
cur = cur.next;
}
for(int i = 0; i < n; i++){
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
ListNode ans = dummy.next;
return ans;
}
}
时间复杂度
最多遍历整个链表一遍
总计为O(n)
做法3
快慢指针
当快指针移到终点时，此时慢指针恰好移动链表的某个点(取决于步差)
1. 初始化：
first = head
second = dummy
这里由于要求的是倒数第n个点的前驱节点
所以，second初始时定义在head的前驱节点dummy
2. 定义两个指针，先让first移动n步
再让first、second同时移动
3. 当first移动到终点时，此时second恰好移动到倒数第n个点的前驱节点。
再将该前驱节点的next指针修改即可
Accode
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0 , head);
ListNode first = head;
ListNode second = dummy;
for(int i = 0; i < n; i++){
first = first.next;//相差n步 计算步差
}
while(first != null){
//移动两个指针
//当first移动到末尾时，此时second移动到倒数第n个点的前驱节点
first = first.next;
second = second.next;
}
//删掉
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
}
时间复杂度
最多遍历整个链表一遍
总计为O(n)
24. 两两交换链表中的节点
解题思路
做法1
递归：每次交换相邻的两个元素
1. 链表为空或者链表中只有一个元素，直接返回head
2. newhead为head.next为要交换的两个元素的第二个元素
3. 原先head.next指向newhead.next交换结果，递归处理下去。
4. newhead.next指向head，为要交换的两个元素的第一个元素，实现两元素交换。
注意：3、4两步不能颠倒过来，原因在于newhead.next被更新过，两次的含义不一样。
第一个newhead.next：指向的是head.next
第二个newhead.next：指向的是head.next.next(递归)
第三个newhead.next: 指向的是head
假如倒过来：
则递归中的newhead.next指向的是head.next而不是head.next.next
代码
class Solution {
//递归：每次交换相邻的两个元素
public ListNode swapPairs(ListNode head) {
//链表为空或者链表中只有一个元素
//直接返回head
if(head == null || head.next == null){
return head;
}
//newhead为head.next
ListNode newhead = head.next;
//原先head的next指向newhead的next交换结果，递归处理下去。
head.next = swapPairs(newhead.next);
//newhead.next指向head，实现两元素交换
newhead.next = head;
return newhead;//返回newhead的结果
}
}
解题思路
做法2
迭代(模拟)
1. 先定义一个哑节点dummyhead,指向head。
2. 再定义一个过渡变量 temp , 初始为dummyhead,用于后续的迭代。
3. 当temp的后两个节点不为空时,交换两个节点。
怎么交换？
先让哑节点(dummyhead)的next指向node2
再让node1.next指向node2.next
再让node2.next指向node1
最后再更新temp为当前的node1，继续迭代即可。
这里的temp不用更新为node1.next while循环写的是当前节点的后两个节点。
代码
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;
}
}
148. 排序链表
解题思路
- 先用快慢指针找到链表中的中点，将整个链表分成两半。
一半是(head,mid)一半是(mid , tail) - 再对两段链表进行排序
- 最后对排序后的两段链表进行合并
时间复杂度
n个节点进行排序，每轮比较所耗时logn
总计为O(nlogn)
Accode
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head , null);//起点是head 终点是null
}
public ListNode sortList(ListNode head , ListNode tail){
if(head == null){//一个节点都没有则返回head
return head;
}
if(head.next == tail){//走到最后一个节点
head.next = null;//先声明head.next为null
return head;//返回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);//排序head 到 mid 这一段
ListNode list2 = sortList(mid , tail);//排序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 比 temp2要小 , temp.next指向temp1
temp1 = temp1.next;//temp1 更新为temp1.next 用于继续比较
}
else{
temp.next = temp2;//temp2 比 temp1要小
temp2 = temp2.next;
}
temp = temp.next;//更新为下一个节点，用于下一次归并
}
//合并两段链表中剩余的节点
if(temp1 != null){
temp.next = temp1;
}
else if(temp2 != null){
temp.next = temp2;
}
return dummyhead.next;//返回头结点
}
}
☀️☀️☀️☀️☀️☀️
后续有补充，持续更新中🌋
喜欢的伙伴点点赞，关个注💗
怎么没更新了，资瓷啊