目录
3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点
1.删除链表中等于给定值 val 的所有节点
给你一个链表的头节点?
head?和一个整数?val?，请你删除链表中所有满足?Node.val == val?的节点，并返回?新的头节点?来源：力扣（LeetCode）
链接：力扣
解题思路：我们想要删除节点，重点就是在于删除原来指向的地址，改为下一个指向的地址
我们在这一题里使用两个指针：一个指向头节点 pre，一个指向头节点的后一个节点 cur
当cur指向的节点是我们要删除的元素，那么我们就修改pre节点指向的地址
将其修改成cur指向的下一个节点，同时cur向后走一步
如果cur指向的节点不是我们要删除的元素，那么我们让pre走到cur的位置上来
同时让cur向后走一步?
我们让pre指向头节点的目的就在于，不会让头节点的位置乱跑
从而导致我们的链表到最后只有一个节点
最后我们贴上代码
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
//如果为空链表直接返回null
ListNode cur = head.next;
ListNode pre = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
cur = cur.next;
} else {
pre = cur;
cur = cur.next;
}
}
if (head.val == val) {
head = head.next;
}
return head;
}2.反转一个单链表
给你单链表的头节点?
head?，请你反转链表，并返回反转后的链表来源：力扣（LeetCode）
链接：力扣
解题思路：
我们要做的是将链表进行反转，反转的效果应该是这样的
?
我们首先应该设置一个cur指向头节点的下一个节点，便于两个节点之间的反转
同时我们还要再设置一个curNext来记录cur的下一个节点，不然的话无法找到往后的节点
再进行第一次反转的时候我们要将头节点指向的地址设置为空，不然会变成死循环
通过画图我们来描述整个过程
?
?
最后我们按照这个思路来完成我们的代码
public ListNode reverseList(ListNode head) {
if (head == null){
return null; //代表空链表没有东西可以反转
}
if (head.next == null){
return head; //代表该链表只有一个节点所以只用反转一次
}
ListNode cur = head.next;
head.next = null; //斩断head与后面节点的联系 不然会陷入死循环
while (cur != null){
ListNode curNext = cur.next;
//在循环里面创建可以减少一行代码 这行代码是 curNext = curNext.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点
?给定一个头结点为?
head?的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
来源：力扣（LeetCode）
链接：力扣
解题思路：利用快慢指针
当我们设置两个指针：一个步长为两步，一个步长为一步
在奇数的链表里，当快指针走到最后一个节点的时候，慢指针刚好走到中间的节点
在偶数的链表里，当快指针走到 null 位置的时候，慢指针刚好走到第二个中间节点
这样设计的原理是，时间相同的情况下，速度快的指针走的路程是慢指针的两倍
所以刚好可以走到中间的节点上
我们贴上代码
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//fast != null && fast.next != null 这样的条件设计可以避免空指针异常
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
} 4.输入一个链表，输出该链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点
来源：牛客
链接：链表中倒数第k个结点_牛客题霸_牛客网
解题思路：我们还是利用快慢指针来解决这道题目
设置两个指针，同时指向头节点
我们先让快指针走了k-1步，然后慢指针与快指针一起走，这样我们就可以找到倒数第K个节点
我们这样做的原理是将倒数第K个节点转换成正数第K个节点
具体是什么意思：我们用图的方式来描述以下这个过程（假设寻找倒数第2个节点）
?
我们在设置快指针的时候我们要注意的是不要让它走到 null 的位置上
不然的话慢指针就会多走一个距离
如果我们将快指针设置成先走K步的话，那么我们就要让快指针走到null的位置上
不然慢指针就会少走一个距离
最后我们贴上代码
public ListNode FindKthToTail(ListNode head, int k) {
ListNode slow = head;
ListNode fast = head;
if(head == null||k <= 0){
return null;
}
while (k - 1 != 0) {
fast = fast.next;
if (fast == null) {
return null;//说明此时为空链表
}
k--;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}5.将两个有序链表合并为一个新的有序链表并返回
将两个升序链表合并为一个新的?升序?链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
来源：力扣（LeetCode）
链接：力扣
解题思路：这题我们要不断的比较两个链表各个值得大小从而串成一个新得链表
我们首先要定义一个虚拟的头节点，通过设置一个指针来将两个链表串联起来
最终才能达到我们想要的效果
我们用图的方式来描述这个流程
?
?
最后当比较短的链表走完以后，我们直接将长链表的剩余部分链接起来?
最后贴上代码
public static MySingleList.ListNode mergeTwoLists(ListNode head1,ListNode head2){
ListNode newHead = new MySingleList.ListNode(-1);
ListNode tmp = newHead;
while (head1 != null && head2 != null) {
if(head1.val < head2.val) {
tmp.next = head1;
head1 = head1.next;
}else {
tmp.next = head2;
head2 = head2.next;
}
tmp = tmp.next;
}
if(head1 != null) {
tmp.next = head1;
}
if(head2 != null) {
tmp.next = head2;
}
return newHead.next;
}6.以给定值x为基准将链表分割成两部分
现有一链表的头指针 ListNode*?pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
来源：牛客
链接：链表分割_牛客题霸_牛客网
?
解题思路：我们设置两个链表，一个链表是存小于X值的数，一个链表是存大于X值得数
每个链表我们要定义两个指针，一个指向头节点，一个用于连接各个值
当我们将所有的值都存好以后，将两个链表链接起来成为一个新的链表
最后就可以的到重新排列以后的链表了
我们在这里面需要注意的是：有可能全部是大于X值的数，有可能是全部小于X值的数
同时我们要手动置空，避免死循环的出现
?
所以我们也要做出相应的改变
最后我们贴上代码
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode be = null;
ListNode bs = null;
ListNode ae = null;
ListNode as = null;
ListNode cur = pHead;
while(cur != null){
if(cur.val < x){
if(be == null){
be = cur;
bs = cur;
}else{
bs.next = cur;
bs = bs.next;
}
}else{
if(ae == null){
ae = cur;
as = cur;
}else{
as.next = cur;
as = as.next;
}
}
cur = cur.next;
}
if(be == null){
return ae;//如果全都是大于X的值那么直接返回第二个链表
}
bs.next = ae;//将两个链表连接起来
if(ae != null){
as.next = null;//手动设置最后一个节点为空，避免出现死循环
}
return be;
}7.链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900
来源：牛客
链接：链表的回文结构_牛客题霸_牛客网
解题思路：我们不妨让两个指针一个指向开头一个指向最后，然后一起向中间走?
如果两个相遇那么说明就是回文结构
想要达到这样的效果我们首先要找到中间节点
这时候就要用到快慢指针来找到中间节点了
当我们找到节点以后
我们想要达到两个指针一起向中间位置走那么就要将中间节点以后的节点进行反转
?反转完毕以后如果就开始不断地对比值是否相等
奇数情况下两个节点要相遇，偶数情况下只要两个值相等就可以结束对比了
?贴上代码
public boolean chkPalindrome(ListNode A) {
// write code here
// write code here
if (A == null) {
return false;
}
if (A.next == null) {
return true;
}
ListNode fast = A;
ListNode slow = A;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode cur = slow.next;
while (cur != null){
ListNode curNext = cur.next;
cur.next =slow;
slow = cur;
cur= curNext;
}
//此时slow刚好指向最后一个节点
//这个时候两个节点一起向中间走
while (A != slow) {
if (A.val != slow.val) {
return false;
}
if (A.next == slow) {
return true;
}
slow = slow.next;
A = A.next;
}
return true;
}8.输入两个链表，找出它们的第一个公共结点
给你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null?
注意，函数返回结果后，链表必须 保持其原始结构 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
解题思路：这题的解题思路与第四题的解题思路类似
我们将两条链表进行比较，得出两者之间得差值
这里的链表差值是公共节点之前的长度差值
定义两个指针，一个指向长的链表，一个指向短的链表
我们先让长的链表走完差值所对应的步长然后再让两个指针一起走
当两个指针刚好相遇的时候，说明走到了公共的节点
?
我们要注意的是有可能两个链表有不相交的情况，这我们也要考虑进去
最后我们贴上代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;//指向最长的
ListNode p2 = headB;//指向最短的
int len1 = 0;//指向最长的
int len2 = 0;//指向最短的
ListNode cur1 =headA;
ListNode cur2 =headB;
while (cur1 != null){
cur1 = cur1.next;
len1++;
}
while (cur2 != null){
cur2 = cur2.next;
len2++;
}
int len = len1 - len2;
if (len < 0){
p1 = headB;
p2 = headA;
len = len2 -len1;
}
while (len != 0){
p1 = p1.next;
len--;
}
while (p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
if (p1 == null){
return null;
}
return p1;
}9.给定一个链表，判断链表中是否有环
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环
如果链表中存在环?，则返回?
true?。 否则，返回?false来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle
我们用力扣上的图片来描述一下题目?
解题思路：
我们利用快慢指针来解决这道题?
?将一个指针设置为 fast?步长为两步作为快指针
将另一个指针设置为 slow?步长为一步作为慢指针
为什么这样设置？
假设链表为有环链表，那么快指针一定先会进入到环内，然后慢指针再进入到环内
如果两个指针相遇那么就可以证明得到链表是有环的
那为什么将步长设置为 fast = 2 slow = 1 而不是其他值？
设置为其他值很有可能会出现跳过相遇不了的情况
假如说我们将 fast = 3，slow = 1?
快指针先进环内，假设在0x56的位置，此时慢指针刚好进环，慢指针在0x13的位置
如果快指针走了三步此时刚好在0x13的位置上，而慢指针此时要向前走一步在0x56
如此循环下去那么永远也相遇不了
我们将这种情况叫做套圈
将快指针设置为 2 慢指针设置为 1 这样他们的相对速度就为 1
这样就可以避免套圈的出现
假设我们将环想象成无限长的跑道，那么慢指针在快指针的前面
因为相对的速度为1，所以随着时间的流逝，不管两者之间的距离有多长
结果都是一定会相遇
并且极端情况是
当fast走完两步刚好走到入环点，此时slow与fast的距离刚好是一个环的距离
那么当slow走完一圈以后回到入环点，fast刚好也走到了入环点
也就是说在这种步长设置的情况下 slow 最多走一个环就可以与fast相遇
最后我们贴上代码
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (slow == fast){
return true;
}
}
return false;
}10.给定一个链表，返回链表开始入环的第一节点
给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
解题思路：想要返回第一个节点，我们首先要证明该链表是一个有环链表
那么我们还是使用第九题的思路，设置两个指针来让他们相遇
指针相遇那么就可以证明链表是一个有环的链表?
如果链表有环，我们假设起点到入环点的距离为X，环的长度为C，相遇点再次走到入环的Y
?
?
我们假设快指针走了一圈就与慢指针相遇了
那么这个时候快指针与慢指针所经历的时间是一样的
我们根据速度推导出公式 t = s/v?
2（X+C-Y）= X+C+C-Y? ? ---->? ? ? X=Y
也就是说当快指针走了一圈就与慢指针相遇的话
那么起点到入环点的距离与相遇点到入环点的距离是一样的
如果我们假设快指针走了N圈，那么还是用公式来推导可以得到以下的结果
?2（X+C-Y）= X+(N-1)C+C-Y? ?---->? ?X = (N-1)C + Y
我们根据结果可以知道
当快指针走完N-1圈以后，再走Y的长度，这个时候快指针刚好走到入环点
而此时，慢指针也刚好走完X的长度，也是刚好走到入环点，两者刚好相遇?
所以我们根据以上的推导
我们不妨让两个指针相遇以后，让快指针留在相遇点，让慢指针回到起点
将他们速度设置为相同的速度，当他们相遇的时候，相遇的位置刚好是入环点
最后我们贴上代码
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (slow == fast){
break;
}
}
//如果没有环的话返回一个null
if (fast == null || fast.next == null){
return null;
}
slow = head;//此时已经相遇了，让慢指针回到原点
while (slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}最后祝大家天天开心，技术越来越强 ：）?