链表(力扣刷题)
1. 基本的解题套路和方法
1.1 反转单链表
链表问题最经典的模版代码
设置三个额外的变量，遍历结束时，pre指向最后一个节点，cur和next都指向null
public ListNode reverseList(ListNode head) {
// 设置额外两个指针
ListNode pre = null;
ListNode cur = head;
ListNode next = null;
//从头反转到尾
while(cur!=null){
// 先记录下一个
next = cur.next;
// 当前的反转
cur.next = pre;
// 更新到下一个, 下面两行代码顺序不可调换！
pre = cur;
cur = next;
}
//指定次数的反转
while(reverseLength-- > 0){
nextNode = curNode.next;
curNode.next = preNode;
// 更新
preNode = curNode;
curNode = nextNode;
}
return pre;
} 1.2 增加dummy节点
在一些删除问题和遍历问题中，为了防止出现单独处理头节点的情况或者头节点被删除，需要换头，可以增加一个虚拟节点，让头节点指向它。
// 设置一个虚拟节点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
while(pre != null){
//对pre.next的一些列操作
pre = pre.next;
}
return dummyNode.next; 1.3 快慢指针
设置两个指针，通常一个快一个慢，一前一后，且他们保持一定的间距，一起遍历链表，结束条件是快指针决定的。
1.4 链表的长度
单链表如果需要统计它的长度可以用如下模版
ListNode cur = head;
int len = 0;
while(cur!=null){
cur = cur.next;
++len;
} 2. 题目
2.1 反转
反转链表
Nr. 206
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
1.迭代方法
略
2.递归方法
比较难以理解，配合动图实用更佳
还有递归方法的详细拆解
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
} 反转链表II
Nr. 92
题目描述:
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
保证1<=m<=n<=链表长度
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解题思路:
设置一个beforeLeft节点，记录前一个反转区域，设置一个afterRight节点，记录最后一个反转的下一个节点。
先找到leftNode节点，从这里进入，开始按照普通翻转方法开始，到结束时，preNode指向rightNode，cur指向afterRight节点。
再根据L是否等于1，决定是否处理头节点。
1.链表原始情况
2.不换头
beforeLeftNode.next = preNode; leftNode.next = curNode; return head;
3.换头
head = preNode; leftNode.next = curNode; return head;
4.整体代码
public static ListNode reverseList(ListNode head, int L, int R){
// 1. 找到反转区域的前一个节点 beforeLeftNode
ListNode beforeLeftNode = null;
// 找到开始反转的右节点
ListNode leftNode = head;
if(L == 1){
beforeLeftNode = null;
leftNode = head;
}else {
// L >= 2
beforeLeftNode = head;
int temp = m;
//注意这里的次数，若temp为2直接跳过while循环
while(--temp>1){
beforeLeftNode = beforeLeftNode.next;
}
leftNode = beforeLeftNode.next;
}
// 2. 先确定反转区域
int reverseLength = R-L+1;
// 从curNode开始是入口
ListNode curNode = leftNode;
ListNode nextNode = null;
ListNode preNode = null;
// R-L+1 次
while(reverseLength-- > 0){
nextNode = curNode.next;
curNode.next = preNode;
// 更新
preNode = curNode;
curNode = nextNode;
}
// 反转完毕，处理头节点 和 两个端节点
// 反转结束时, 和普通反转链表一样，preNode指向反转的最后一个节点，cur和next都指向下一个节点
if (L == 1){//考虑要换头节点
head = preNode;
System.out.println("换头了");
}else {
beforeLeftNode.next = preNode;
}
leftNode.next = curNode;
return head;
} 链表k个一组反转
Nr.25
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
解题思路:
每个k组反转，都要找到他们的前驱节点，但是以头节点开始的那一组没有前驱节点，因此定义一个假的节点，假节点的next指向head。
dummy->1->2->3->4->5初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点
当end不为null, end先遍历k次到指定位置，如果剩下的链表长度不足K，立刻退出，不用反转；
找到本次链表的开始节点start, 它也是反转结束后的最后一个节点，也会是本次更新的pre和end;
再记录下次要反转的部分的开头, next;
断开本次k长度的部分,方便反转链表的子函数;
执行局部反转, 返回反转后的头节点;
start.next会因为反转函数变为null，通过.next把断开的链表重新链接。
public static ListNode reverseKGroup(ListNode head, int k){
if (head == null || head.next == null){
return head;
}
// 需要两个节点 pre 和 end，分别记录反转区域的前缀和最后一个反转区域
// 建立一个虚拟节点dummy, 记录头节点的前缀
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
// 建立两个节点 start 和 next, 分别记录开始反转的节点 和 下一批要反转的节点
while(end!= null){
// end 遍历k次到指定位置
for(int i=0; i<k && end!=null; i++){
end = end.next;
}
if (end == null){
// 剩下的链表长度不足K，立刻退出，不用反转
break;
}
// 找到本次链表的开始节点, 它也是反转结束后的最后一个节点，也会是本次更新的pre和end
ListNode start = pre.next;
// 记录下次要反转的部分的开头
ListNode next = end.next;
// 断开本次k长度的部分
end.next = null;
// 执行局部反转, 返回反转后的头节点
pre.next = reverseList(start);
// start.next会因为反转函数变为null，通过.next把断开的链表重新链接。
start.next = next;
pre = start;
end = start;
}
return dummy.next;
} 2.2 删除
删除链表节点(力扣版)
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
请在这里输入引用内容
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
解题思路:
设置一个虚拟节点，防止删除的节点是head，这样分情况讨论很麻烦。
public ListNode deleteNode(ListNode head, int val) {
if(head == null){
return null;
}
// 设置一个虚拟节点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
while(pre!=null){
// 发现待删除的点
if(pre.next.val == val){
// pre.next -> cur, pre指向下一个节点，绕过待删除节点
pre.next = pre.next.next;
// 结束循环
break;
}
pre = pre.next;
}
return dummyNode.next;
} 删除链表节点(剑指版)
待删除节点不是以val给出，而是以ListNode的形式给出的。如何做到时间复杂度O(1)。
解题思路:
类似于乾坤大挪移，把待删除节点的后一个元素赋值(val和next)给待删除节点，也就相当于删除了当前元素。
如果删除的节点是尾节点，就需要从头遍历到尾节点的前一个节点，把它删除。这个复杂度是O(n)。但最后的平均复杂度是O(1)。
class deleteNode {public static ListNode deleteNode(ListNode head, ListNode val){
if (head == null || val == null){
return null;
}
if (val.next != null){ // 待删除节点不是尾节点
ListNode next = val.next;
val.val = next.val;
val.next = next.next;
} else if (head == val){ // 待删除节点只有一个节点，此节点为头节点
head = null;
} else { // 待删除节点为尾节点
ListNode cur = head;
while (cur.next != val){
cur = cur.next;
}
cur.next = null;
}
return head;
}
} 掌握了这个思想，这道题就可以秒了, 删除中间节点
删除排序链表中的重复元素 II
Nr.82
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例 1:
请在这里输入引用内容
输入: 1->2->3->3->4->4->5
输出: 1->2->5
解题思路:
链表可能会删除头节点，因此设置一个虚拟节点dummy。并设置快慢指针，其中当慢指针和快指针相等时，说明相邻节点是相等的，让快指针一直遍历到不相等的位置，把它们一并删除。
public ListNode deleteDuplicates(ListNode head) {
// 边界条件: 空链表，只有一个节点的链表，不会发生删除
if(head == null || head.next == null){
return head;
}
// 先建立虚拟节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode left = dummy;
ListNode right = head;
// 开始遍历，直到right到达最后一个节点, 这里的第一个条件是兼顾到内层的while循环
// 因为比较的是right.next，所以它不能为null
while(right!=null && right.next!=null){
// 如果不相等，则向下遍历
if(left.next.val != right.next.val){
left = left.next;
right = right.next;
}else{ // 有相同节点
// 逻辑判断的短路效应: 条件的顺序是有关系的
// 遍历到不相等的位置，退出循环时left在相等节点的前一个，right在不相等节点
while(right!=null && left.next.val==right.val){
right = right.next;
}
// 让left指向right，跳过所有的相等节点
left.next = right;
}
}
return dummy.next;
} 删除排序链表中的重复元素
Nr. 83
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
请在这里输入引用内容
输入: 1->1->2
输出: 1->2
解题思路:
和82相比，这道题我们可以推断出，头节点一定不会被删除，因为是升序链表，因此不用设置虚拟节点，直接用快慢指针解决。因为没有虚拟节点，不用像82那样比较快慢指针的next，而是直接比较。
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return null;
}
ListNode left = head;
ListNode right = head.next;
while(right!=null){
// 不相等时，遍历到下一个，始终保持快慢间距
if(left.val != right.val){
left = left.next;
right = right.next;
}else{
// 找到不相等的点
while(right!=null && left.val == right.val){
right = right.next;
}
// 退出循环时，right为不相等的第一个数, left为第一个相等的数
left.next = right;
}
}
return head;
} 2.3 交点/环/合并
两个链表的第一个公共节点
Nr. 剑指 Offer 52.
输入两个链表，找出它们的第一个公共节点。
解题思路:
设置两个指针，一起遍历，若有公共交点一定是两个指针同时到达，所有第一种思路是统计两个链表的长度，让长链表的指针先走，走到短链表的头，然后再一起走。
另一种就是，两个指针从头一起遍历，当到达末尾时，让两个指针分别指向对方的头节点，若有交点，一定会相遇。若没有交点，最后一起为null，退出循环。原理就是短链表的快指针走得快，让他再去长链表遍历，最后会一起同步。
原理是, 两个链表长度分别为L1+C、L2+C， C为公共部分的长度，第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时相交。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
// 虐狗法
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = p1 != null ? p1.next : headB;
p2 = p2 != null ? p2.next : headA;
}
return p1;
} 合并两个排序的链表
Nr. 剑指 Offer 25
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
请在这里输入引用内容
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解题思路:
类似于，归并排序的思想，双指针，谁小移动谁，合并。设置一个虚拟节点模拟排序后链表的头部的前一个节点，依次添加节点，最后返回dummy.next。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 合并到第一个元素较小的链表中
if(l1 == null && l2 == null){
return null;
}
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
// 用虚拟节点来记录，最后要返回的头节点信息
ListNode dummyNode = new ListNode(-1);
ListNode cur = dummyNode;
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 dummyNode.next;
} 环形链表
Nr. 141
给定一个链表，判断链表中是否有环。
解题思路:
我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。但是这种方法的空间复杂度是O(n)。
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
} 进阶方法，借助快慢指针，让快指针每次走两步，慢指针走一步，如果链表有环，二者一定会相遇，可以想像在环形赛道内，一个运动员跑得慢一个跑得快，最后一定会套圈相遇。定量分析就是：二者的距离／速度差。
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
// 采用快慢指针的方法
ListNode f = head;
ListNode s = head;
// 在环内追逐
boolean res = false;
// 如果没有环，一定是fast先出条件
while(f!=null && f.next!=null){
f = f.next.next;
s = s.next;
if(f == s){
return true;
}
}
return res;
} 环形链表 II
Nr. 142
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
解题思路:
和141类似可以用哈希表，找到第一个出现过的节点就是入环节点，但缺点就是空间复杂度高。现在介绍进阶方法。详细参考
设置两个指针，一快一慢，快的(f)每次走两步，慢的(s)每次走一步。如果链表没有环，f指针会先到达null退出循环，表示无环。
如果有环，f和s一定会在环内某个位置相遇，假设环外节点a步，环内节点b步，接下来计算他们相遇时走了多少步，f每次走两步都统计进去。f指针比s多走二倍，所以f=2s，并且它们都走过了环外节点a步，且在环内转圈后相遇，因此f=s+nb，表示f走过s的步数，且在圈内多转了n次。
f = 2s 和 f = s + nb可以得出重要结论一: s=nb，就是说慢指针在相遇时已经走了nb步。
现在想要到达入环节点，每个从头节点出发走过a+nb步后都会在入环节点，因为nb是整数圈，最后还是会在入环节点处。第二个重要结论就是：慢指针只要走过a+nb步就会在入环节点处，它已经走了nb步，就差a步，借助f指针帮助它，让f在第一次相遇后，回到头部，和s指针一起走，当相遇时，一定是在入环节点。
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
// 快慢指针第一次相遇，慢指针走了 nb步
while(true){
// 可以遍历到null，链表没有环
if(fast==null || fast.next==null){
return null;
}
// 有环
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
// 相遇时，跳出循环
break;
}
}
// 此时快指针移动到头部，再走a步，慢指针也走a步，走a+nb步，一定到入环节点
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
} 2.4 链表长度
倒序打印链表
Nr. 剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
请在这里输入引用内容
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
解题思路:
用模版统计出链表的长度，然后分配一个数组，再从头遍历链表，把值从尾到头的填入数组中。
public int[] reversePrint(ListNode head) {
if(head == null){
return new int[0];
}
// 第一次遍历，希望得到链表的长度
ListNode cur = head;
int len = 0;
while(cur!=null){
cur = cur.next;
++len;
}
// 新建数组
int[] res = new int[len];
cur = head;
int index = len-1;
while(cur!=null){
res[index] = cur.val;
cur = cur.next;
--index;
}
return res;
} 链表中倒数第k个节点
Nr. 剑指 Offer 22
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
请在这里输入引用内容
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
解题思路:
一种思路是统计处链表的长度，再去遍历到len-k的节点，这样不能一次遍历完。而快慢指针可以做到一次遍历完，且不用处理一些数值关系。
思路就是，让快指针先走k步，慢指针在头节点，一起遍历，当快指针到达null时，慢指针此刻就在倒数k的位置。
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null || k==0){
return null;
}
// 设置快慢指针
ListNode former = head;
ListNode latter = head;
// 快指针先走k步
while(k-- >0){
// k 设置的超过链表长度，不合理
if(former == null){
return null;
}
// 假设是倒数第k节点，最后一次，fomer=null
former = former.next;
}
// 一起移动，直到快指针先到达尾部
while(former!=null){
former = former.next;
latter = latter.next;
}
return latter;
} 2.5 复制链表
复制一种复杂链表
Nr. 剑指 Offer 35.
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
解题思路:
这个是链表的深度拷贝，每个节点都是新建立，关键在于如果复制random的关系。可以用哈希表记录一种映射，老节点对应新节点。
遍历新节点，同时也是遍历老节点，给新节点建立他们自己的next和random关系。方法是，找到老节点的next，再通过哈希表找到对应的新节点的，同理random也是。空间复杂度是O(n)，时间复杂度O(n)
// 完成一种深度拷贝
public Node copyRandomList(Node head) {
// 哈希表的方法
// 用哈希表记录，老节点 和 新节点
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while(cur!=null){
map.put(cur, new Node(cur.val));
cur = cur.next;
}
// 接下来为新节点，设置它们的 next 和 random
cur = head;
while(cur!=null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = cur.random == null ? null : map.get(cur.random);
cur = cur.next;
}
return map.get(head);
} 另一种方法可以做到空间复杂度O(1)，方法就是把新链表的节点都挂在老链表的后表，这样我们也仿照哈希表，建立起新老节点的映射关系，老得Node.next 是 新的Node。
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// 空间复杂度为O(1)的方法，用老节点后面跟着新节点，代替了hash表
Node cur = head;
Node next = null;
// 每次把新产生的节点放在老节点的后面
while(cur!=null){
// 记录老节点的下一个
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
// 设置新节点的 random
// 先找到老节点的random，新节点的random就是它的next
cur = head;
Node curCopy = null;
while(cur!=null){
// 记录老节点的下一个, 这次加倍了
next = cur.next.next;
// 新节点
curCopy = cur.next;
curCopy.random = cur.random == null ? null : cur.random.next;
cur = next;
}
// 把新老节点拆分开，恢复成原有的样子
// 重新设置每个节点的next
cur = head;
Node res = head.next;
while(cur!=null){
// 记录老节点的下一个, 这次加倍了
next = cur.next.next;
curCopy = cur.next;
curCopy.next = next==null ? null : next.next;
cur.next = next;
cur = next;
}
return res;
} 
