LeetCodeHot100_0x04
25.环形链表
求解思路： 首先，哈希秒杀，存节点，只要出现相同节点就有环。
其次、链表题很喜欢用到双指针，所以这题优先考虑双指针。我们可以定义一对快慢指针，如果链表没有环，可以保证fast指针优先遍历完链表，然后返回false；如果链表有环，则会不断进入循环，直到快慢指针一定有某一次发生相遇，返回true。
【快慢指针法】
public class Solution {
public boolean hasCycle(ListNode head) {
// 快慢指针 有环必相遇，没环fast为空
ListNode fast = head;
ListNode solw = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
solw = solw.next;
if(fast == solw) return true;
}
return false;
}
}
26. 环形链表Ⅱ(不会)
求解思路： 这题只能想到哈希法，判断有无重复节点，返回即可。
参考题解的快慢指针法，关键在于数学关系推导。
【哈希法】
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> hs = new HashSet<>();
ListNode node = head;
while(node != null && node.next != null) {
if(!hs.isEmpty() && hs.contains(node)) {
return node;
}
hs.add(node);
node = node.next;
}
return null;
}
}
【快慢指针法】
下图来自于LeetCode官方题解，我借助下图进行讲解总结
设环外长度为a，当slow指针走到环扣时，fast指针必然在环内（紫色点），记录此时slow指针距离fast指针距离为b，剩余距离为c；假设fast已经走过n圈，此时：
- slow走过的长度： a
- fast走过的长度：a + n(b + c) + b
由于fast指针永远比slow指针快1个单位的速度，现在可以看作fast指针还差c个单位可以追上A点的slow；所以当：
- slow走过的长度：a+c
- fast走过的长度：a+n(b+c)+b+2c
两者重合，根据二倍关系化简式子：
a + (n+1)b + (n+2) c = 2a + 2c
-------> a = (n+1)b + nc
------->b + n(b + c)
这下好了，发现规律了，环外距离a的长度等于 b + n 倍的环内长度，其中b是fast 和 slow相遇点（距离环口的距离），所以我们只需要再定义一个指针pre，让它和慢指针一起走，相遇的时候，就是环口了。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ListNode pre = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
while(pre != slow) {
pre = pre.next;
slow = slow.next;
}
return pre;
}
}
return null;
}
}
27. 合并两个有序链表（不熟）
求解思路： 新开一个链表，遍历每次把当前两个链表种较小的值加入。
之所以不熟，还是对链表的理解太弱了。直接去操作头节点，然后又忘记指针移位，导致调试了好多次都是错误的。
【双指针法】
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newList = new ListNode();
ListNode current = newList; // 当前指针，用于构建新链表
if(list1 == null) return list2;
if(list2 == null) return list1;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
}else {
current.next = list2;
list2 = list2.next;
}
current = current.next; // 移动指针
}
if(list1 != null) {
current.next = list1;
}
if(list2 != null) {
current.next = list2;
}
return newList.next;
}
}
28. 两数相加（链表版）
求解思路： 有了上一题合并两个有序链表的经验后，这一题写的就很轻松了。咱直接模拟小学生学加法进位，用链表实现即可。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
ListNode ans = new ListNode();
ListNode curr = ans;
int k = 0;
while(l1!=null && l2!=null) {
int value = (l1.val + l2.val + k) % 10;
k = (l1.val + l2.val + k) / 10;
curr.next = new ListNode(value);
curr = curr.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1!=null) {
if(k!=0) {
int value = (l1.val + k) % 10;
k = (l1.val + k) / 10;
curr.next = new ListNode(value);
curr = curr.next;
l1 = l1.next;
}else{
curr.next = l1;
break;
}
}
while(l2!=null) {
if(k!=0) {
int value = (l2.val + k) % 10;
k = (l2.val + k) / 10;
curr.next = new ListNode(value);
curr = curr.next;
l2 = l2.next;
}else{
curr.next = l2;
break;
}
}
if(k!=0) {
curr.next = new ListNode(k);
}
return ans.next;
}
}
29. 删除链表的倒数第N个节点
求解思路： 逆向思维求解或递归求解
【逆向思维】删除倒数节点，可以先求出节点数再正向找等效位置的节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 先遍历一遍计算结点数，在正向删不就好了
ListNode curr = head;
int cnt = 0;
while(curr != null) {
cnt++;
curr = curr.next;
}
if(n==cnt) return head.next; // 删除头节点的情况
int k = cnt - n; // 需要删除节点的前一个节点
curr = head;
while(--k > 0) {
curr = curr.next;
}
curr.next = curr.next.next;
return head;
}
}
【递归法】
class Solution {
private int cnt = 0;
public ListNode removeNthFromEnd(ListNode head, int n) {
// 递归写法，先深入到尾节点，然后递归回溯
if(head == null) return null;
head.next = removeNthFromEnd(head.next,n);
cnt++;
if(n==cnt) return head.next;
return head;
}
}
30. 两两交换链表中的节点
求解思路： 链表题做多了，类型很固定，基本上考察指针遍历和递归思想。
【双指针变量】
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode p = head;
ListNode q = head.next;
while(p != null && p.next != null){
q = p.next;
int temp = q.val;
q.val = p.val;
p.val = temp;
p = q.next;
}
return head;
}
}
【递归法】看了题解理解的，链表题在遍历中总喜欢采用自底向上的思想，代码很简洁，但是可读性不是很好。
class Solution {
public ListNode swapPairs(ListNode head) {
// 1. 递归出口： 没有或只要一个的时候不用交换了
if(head == null || head.next == null) {
return head;
}
// 原链表是1->2->3->4。
// 调用swapPairs(1)的时候，newHead是2。
// 然后需要处理head.next = swapPairs(newHead.next)，即swapPairs(3)。
// 这时候进入处理3->4的递归层。
// 在处理swapPairs(3)的时候，newHead是4，
// 然后处理swapPairs(4.next)也就是swapPairs(null)。
// 返回null，所以3的next是null。
// 然后newHead（4）的next指向3，返回4。
// 所以在处理3->4的递归层，返回的是4->3。
// 回到最初的层，此时head是1，它的next被设置为4->3，
// 所以链表变成1->4->3。
// 然后newHead是2，它的next被设置为1，
// 所以整个链表变为2->1->4->3。这样就完成了交换。
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
31. k个一组翻转链表（递归不会）
求解思路： 这个一眼看又是考递归了（雾），但是还是那句话，链表题不会建议转成数组来做，最后把值再填回去就好了。
【反值不反向】时间O(N)、空间O(N)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 反值不反向
List<Integer> value = new ArrayList<>();
ListNode curr = head;
// 值放数组
while(curr != null) {
value.add(curr.val);
curr = curr.next;
}
// 按要求调转值
int n = value.size();
for(int i=0;i<n/k;i++) {
int l = i*k;
int r = Math.min(((i+1) * k - 1),n-1);
while(l<=r) {
int temp = value.get(l);
value.set(l,value.get(r));
value.set(r,temp);
l++;r--;
}
}
// 将值填充回链表
int cnt = 0;
curr = head;
while(curr != null) {
curr.val = value.get(cnt);
cnt++;
curr = curr.next;
}
return head;
}
}
32. 总结：
写给自己：今天是LeetCodeHot100第四天，刷了31题，距离一天10题的目标还是有不小差距的。但是10道题确实也很吃我状态，有时候题目稍微难一点我就想抓狂。另外就是最近同步准备面试之类的事情，没办法一整天都在刷题。以前也立下过刷hot，但是都打卡几天就失败了。这次写博客其实也是希望提醒自己，菜真的要多练。
题目总结：
今天很纯粹的链表题：
- 环形链表
哈希、双指针- 判断环可以用哈希找是否有重复节点出现；或者快慢指针
- 环形链表Ⅱ
双指针、思维- 判断环口位置，需要用到快慢指针，存在一个数学推导过程
- 合并两个有序链表
双指针- 跟归并排序的思路差不多
- 两数相加链表版
双指针、模拟- 双指针模拟小学生加法运算过程，注意进位
- 删除链表中倒数第N个节点
逆向思维、递归- 可以将倒数第N个点问题转换为正数第M个；或者用递归的回溯解决链表单向的限制
- 两两交换链表中的节点
双指针、模拟、递归- 两个指针维护前后两个节点，再交换就可以了；用递归也很优雅
- k个一组翻转链表
变通思维、递归- 链表改向麻烦，可以把值按要求给重排再放回去，一样可以达到目的。
总结：链表题常与 哈希表、双指针、递归算法相关联。遇到不会的链表题，可以尝试先将链表结构转换成更为熟悉的数组结构，再解决数组问题，最后再转换成链表。