单链表经典面试题 (动图解析)
🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!
人生格言：当你的才华撑不起你的野心的时候,你就应该静下心来学习!欢迎志同道合的朋友一起加油喔🦾🦾🦾
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个🐒嘿嘿
谢谢你这么帅气美丽还给我点赞！比个心
目录
1.反转链表
1.1 题目展示及写题链接
1.2 解决思路+过程展示
1.3 实现代码
2.求单链表的中间结点
2.1 题目展示及写题链接
2.2 解决思路+过程展示
2.3 实现代码
3.求单链表的倒数第k个结点
3.1 题目展示及写题链接
3.2 解决思路+过程展示
3.3 实现代码
4.合并两个有序链表
4.1 题目展示及写题链接
4.2 解决思路+过程展示
4.3 实现代码
5.回文串
5.1 题目展示及写题链接
5.2 解决思路+过程展示
5.3 实现代码
6.链表分割
6.1 题目展示及写题链接
6.2 解决思路+过程展示
6.3 实现代码
7.相交链表
7.1 题目展示及写题链接
7.2 解决思路+过程展示
7.3 实现代码
8.环形链表
8.1 题目展示及写题链接
8.2 解决思路+过程展示
8.3 实现代码
9.环形链表||
9.1 题目展示及写题链接
9.2 解决思路+过程展示
9.3 实现代码
1.反转链表
1.1 题目展示及写题链接
● 题目展示
● 写题链接:力扣
1.2 解决思路+过程展示
● 解决思路：
1).将整个链表结点一一取出进行头插
2).使用curNext结点保存cur的下一个结点，避免后续结点丢失
3).当前的头结点的next要置空，否则会使单链表成环
● 过程展示(已排除特殊情况，特殊情况于代码中解释)：
1.3 实现代码
class Solution {public ListNode reverseList(ListNode head) {//当链表为空直接返回null，如果链表只有一个结点，则直接返回该结点if(head == null || head.next == null) return head;//游标结点ListNode cur = head.next;head.next = null; //避免链表成环//进行头插while(cur != null) {ListNode curNext = cur.next; //保存游标结点的下一结点cur.next = head; //当前cur的next域指向头(头插)head = cur; //更新headcur = curNext; //游标更新到下一个结点}return head; //反转完毕，返回头结点}
}在数据结构和算法中,游标节点通常是指一个临时变量，用于在遍历、查找、修改或删除数据结构（如链表、树等）中的元素时，作为当前处理或访问的节点。
2.求单链表的中间结点
2.1 题目展示及写题链接
● 题目展示：
● 写题链接：力扣
2.2 解决思路+过程展示
● 解决思路：
★快慢指针(重点掌握，有大用处!):
慢指针走一步，快指针走两步。这里分两种情况。
情况一：当链表结点个数为偶数时，快指针为null结束遍历
情况二：当链表结点个数为奇数时，快指针的next域为空结束遍历。
● 过程展示(以情况一做展示)
2.3 实现代码
class Solution {public ListNode middleNode(ListNode head) {//如果链表为空或只有一个结点都返回它本身if(head == null || head.next == null) return head;//快慢指针ListNode slow = head; //慢指针ListNode fast = head; //快指针while(fast != null && fast.next != null) {slow = slow.next; //慢指针走一步fast = fast.next.next; //快指针走两步}return slow;}
}3.求单链表的倒数第k个结点
3.1 题目展示及写题链接
● 题目展示：
● 写题链接：链表中倒数第k个结点_牛客题霸_牛客网
3.2 解决思路+过程展示
● 解决思路(这里不借用整型变量进行计数，即让游标结点走 ：链表总长度 - k 步)：
★快慢指针：
1) 先让快指针走k - 1步。
注:设慢指针为倒数第k个结点，那么它与快指针直接总是相差k - 1个结点。
2) 然后再和慢指针一起走，直到快指针的next域为空，那么慢指针就是倒数第k个结点。
● 过程展示(假设k = 3)：
3.3 实现代码
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {//只要链表为空或k小于等于0链表的倒数第k个结点都为nullif(head == null || k <= 0) return null;//让fast走k-1步ListNode fast = head;ListNode slow = head;while(k - 1 != 0){fast = fast.next;k--;}//当k>链表结点总个数时，倒数第k个结点为空if(fast == null) return null;//和slow同时走，直到fast.next为空while(fast.next != null) {slow = slow.next;fast = fast.next;}return slow;//返回slow}
}4.合并两个有序链表
4.1 题目展示及写题链接
● 题目展示：
● 写题链接：力扣
4.2 解决思路+过程展示
● 解决思路：
1) 设置虚拟哨兵结点用于返回合并之后的链表，游标结点用于进行合并链表结点的新增
2) 链表一和链表二进行一起遍历，它们的哪个结点值小，就往合并链表中插入，它们也不断后移，直到其中一个链表的结点遍历完毕。
3) 两个链表的结点个数不一定相同，结点个数多的那一个链表需要继续添加到合并链表中
● 过程展示：
4.3 实现代码
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//三种特殊情况 if(list1 == null) return list2; //链表一为空，则合并之后的链表为链表二if(list2 == null) return list1; //链表二为空，则合并之后的链表为链表一if(list1 == null && list2 == null) return null; //两个链表都为空，则合并之后的链表也为空//虚拟哨兵结点ListNode head = new ListNode();ListNode cur = head; //游标结点while(list1 != null && list2 != null) {if(list1.val < list2.val) { //哪个链表的结点值小，则插入哪个结点cur.next = list1;cur = list1;list1 = list1.next;}else {cur.next = list2;cur = list2;list2 = list2.next;}}//链表一剩下的结点if(list1 != null){cur.next = list1;}//链表二剩下的结点if(list2 != null){cur.next = list2;}return head.next; //返回哨兵结点的下一个}
}5.回文串
5.1 题目展示及写题链接
● 题目展示：
写题链接：链表的回文结构_牛客题霸_牛客网
5.2 解决思路+过程展示
● 解决思路：
1) 先找到整个链表的中间结点。
2) 将整个链表子区间(中间结点~最后一个结点)反转
3) 从两边向中间进行判断，两端结点值是否相等，不相等则返回false，在整个遍历结束后，如果没有返回false，那么该链表是回文结构，返回true。
● 过程展示：
5.3 实现代码
public class PalindromeList {public boolean chkPalindrome(ListNode A) {//特殊情况:链表为空和链表只有一个结点的时候都返回trueif(A == null || A.next == null) return true;//1.求链表的中间结点(快慢指针)ListNode slow = A;ListNode fast = A;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}//2.反转链表子区间(slow~最后一个结点)ListNode cur = slow.next;while(cur != null){ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//从两边向中间进行判断while(A != slow) {if(A.val != slow.val) return false;if(A.next == slow) return true; //结点个数为偶数时，避免空指针异常A = A.next;slow = slow.next;}return true;}
}6.链表分割
6.1 题目展示及写题链接
● 题目展示
● 写题链接：链表分割
6.2 解决思路+过程展示
● 解决思路
1）准备两个链表，一个链表存值小于x的结点(aHead首结点)，另一个链表值存大于x的结点(bHead首结点)。
注:为方便最后将两个链表链接所以要保存两个链表的首结点,而尾结点是为了便于尾插。
2）对原始链表进行遍历，通过判断游标值的大小，分别对两个子链表进行尾插。
3）遍历完毕后，分为三种情况返回：
① 情况一:原始链表中所有结点都大于x → 返回bHead
② 情况二：原始链表中所有结点都小于x → 返回aHead
③ 情况三：原始链表中既有小于x的结点也有大于x的结点 → 与bHead链接后，返回aHead。
注:当原始链表中最后一个结点值小于x时，那么bHead链表最后一个结点的next就会不为空，那么链接到aTail后，形成的链表就为环形链表，所以不管原始链表中最后一个结点值是否小于x，我们都要将bTail(最后一个结点).next域赋空。
● 过程展示
6.3 实现代码
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code here//1.准备要分割的俩个区间的头和尾ListNode aHead = null,aTail = null; //小于x的结点子链表的头和尾ListNode bHead = null,bTail = null; //大于x的结点子链表的头和尾//2.遍历整个链表进行两个子链表的尾插(不会改变原来的数据顺序)ListNode cur = pHead; //游标结点while(cur != null) {if(cur.val < x) {if(aHead == null) { //子链表为空游标结点则直接等于其首结点aHead = cur;aTail = cur;}else {aTail.next = cur; //尾插aTail = aTail.next;}}else {if(bHead == null) { //子链表为空游标结点则直接等于其首结点bHead = cur;bTail = cur;}else {bTail.next = cur; //尾插bTail = bTail.next;}}cur = cur.next;}//3.如果两个子链表都不为空则将两个子链表进行链接if(aTail == null) return bHead; //特殊情况一:pHead链表中所有结点均大于x//链接(普通情况:pHead链表中有大于也有小于x的结点 //和特殊情况二:所有结点都小于x皆返回aHead)//注:如果pHead链表中最后一个结点如果小于x的话,一定要将bTail.next置空不然会成为环形链表if(bHead != null) bTail.next = null; aTail.next = bHead; return aHead;}
}7.相交链表
7.1 题目展示及写题链接
● 题目展示 
● 写题链接：相交链表
7.2 解决思路+过程展示
● 解决思路
1）因为两个原始链表不可改动，所以我们使用两个游标结点遍历它们，求出它们的长度。
注:遍历完毕后一定要恢复两个游标结点，方便最后重新进行遍历。
2）求出它们之间的长度差值，让链表长度较大的那个链表先走差值步。
3）最后让两个游标结点同时走，直到它们相等，那么它们所在的结点就是两个链表的相交结点，返回它们中任意一个都可以。
● 过程展示
7.3 实现代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//1.准备遍历headA和headB的游标结点ListNode curA = headA,curB = headB;//2.在相交之前，让两个链表的结点个数一样int lenA = 0,lenB = 0;while(curA != null) {lenA++;curA = curA.next;}while(curB != null) {lenB++;curB = curB.next;}//恢复两个游标结点curA = headA;curB = headB;int len = lenA - lenB;if(len < 0) {curA = headB;//让curA一直都是存链表长度较大的那个链表curB = headA;//让curB一直都是存链表长度较小的那个链表len = lenB - lenA; //len一直大于或等于0}//3.让链表长度较大的那个链表先走len步，让它和链表长度较小的链表同步起来while(len != 0) {curA = curA.next;len--;}//4.同时走直到到相交结点while(curA != curB) {curA = curA.next;curB = curB.next;}return curA;}
}8.环形链表
8.1 题目展示及写题链接
● 题目展示
● 写题链接：环形链表
8.2 解决思路+过程展示
● 解决思路
快慢指针：慢指针走一步，快指针走两步。
如果快指针和慢指针最后相遇，则链表中存在环，反之，则不存在。
注:快指针走的速度是慢指针走的速度的两倍，如果链表中有环的话，进入环之后，它们的距离是一定的(最大为环的长度)，那么慢指针和快指针的距离会随着它们的不断移动，距离会慢慢缩小，直到它们两相遇，则能链表中有环。
● 过程展示
8.3 实现代码
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head,fast = head;while(fast != null && fast.next != null) {slow = slow.next; //走一步fast = fast.next.next; //走两步if(slow.equals(fast)) return true; //是否相遇}return false; //没有相遇}
}9.环形链表||
9.1 题目展示及写题链接
● 题目展示
● 写题链接：环形链表||
9.2 解决思路+过程展示
● 解决思路
快慢指针：慢指针走一步，快指针走两步。
如果快指针和慢指针最后相遇，则链表中存在环，不存在环直接返回null，将慢指针恢复到原始链表的头，fast在链表环中它们的相遇点，两个指针同时(慢指针和快指针都一步一步地走)行走，再次相遇点就是链表开始入环的第一个节点。
● 过程展示
这道题需要推导出一个公式：看完图解基本上就能懂了：
9.3 实现代码
public class Solution {public ListNode detectCycle(ListNode head) {if(head == null) return null;//1.先判断链表是否有环(快慢指针)ListNode slow = head,fast = head;boolean flag = false;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow.equals(fast)) {flag = true;break;}}if(flag) {//2.再同时走直到相遇slow = head;//恢复慢指针while(!slow.equals(fast)) { //同时走(都一步一步的走)slow = slow.next;fast = fast.next;}return slow;}else {return null;}}
}不管是大环还是小环，其实我们只要推导出 X = Y 这个公式，让其中一个指针指向 head，另一个指针指向相遇点，两者以相同的速度走，大环的情况，两个指针走的路程分别是 X,Y, 最后在入环点相遇；小环的情况，两个指针走的路程分别为 X, (N-1)C, 也就是说，从相遇点开始走的那个指针在小环里面转了很多圈之后，最后走个 Y 的距离就与另一指针相遇了。
