?作者简介:大家好,我是小鱼儿,大家可以叫我鱼儿目录
博客首页:是小鱼儿哈
系列专栏:一起刷好题
每日一句:努力不是重点,常态化才是关键。真正努力的人,能随时进入任何角色,在过程中找到感觉和快乐。
博主也在学习阶段,如发现问题请告知,非常感谢
一、输出链表的倒数第k个结点
二、链表分割
【一起刷好题|《牛客每日一题》链表分割、输出链表的倒数第k个结点】
一、输出链表的倒数第k个结点
题目链接:输出链表的倒数第k个结点
文章图片
思路一:通过遍历链表,求得链表的长度,然后求得返回的是正数的第一个结点
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { ListNode cur = head; int count = 0; while (cur != null) { cur = cur.next; count++; // 通过遍历求出链表的结点数目 } if (k > count) return null; // 当k > 链表的长度时,直接返回null if (head == null || k <= 0) return null; // 处理特殊情况 ListNode tmp = head; // 倒数第k个结点,就是相当于是正数第count - k个结点 for (int i = 0; i < count - k; ++i) { tmp = tmp.next; } return tmp; // 相当于是把倒数第k个结点之后的那一串结点给返回了 } }
思路二、不求长度,用双指针来做
即快指针fast先走k步,然后慢指针slow再开始走,当fast走到链表的结尾时,slow刚好走到倒数第k个结点处(代码里有详细解释)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k <= 0) return null;
// 处理特殊情况
// 定义两个快慢指针
ListNode fast = head, slow = head;
for (int i = 0;
i < k;
++i) { // 即fast先走k步
if (fast == null){
return null;
}
else {
fast = fast.next;
}
}
// 之后fast和slow再一起走,当fast走到链表的结尾处时,slow刚好走的链表第k个结点处
// 为什么呢?因为比方倒数第k个结点是正数第m个结点,那么m + k == 链表的长度,
// fast先走了k个结点,那么fast再走m个结点不就正好到链表结尾了吗?此时slow不就刚好走了k个结点吗!
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
// 返回该结点
}
}
有小伙伴可能会问了for循环里的判断是什么意思呢?
主要是处理 k > 链表的长度这种情况
当循环这个位置(If 语句里)出现fast等于null的情况,说明一定是k > 链表的长度
因为if语句判断fast是否为空我放在了前面,即使k == 链表的长度,此时在这个位置fast也不可能为空,最多经过了下面的fast = fast.next此时才为空,但同时这个时候循环马上就要退出了
所以当在if(里出现fast 为空的情况时候,一定是 K > 链表的长度
二、链表分割
题目链接
链表分割——牛客
文章图片
思路:设置两个链表头,遍历原链表,一个追加小数链表,一个追加大数链表,最后将小数链表粘到大数链表前边即为结果。
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
if (pHead == null) return pHead;
// 为了便于操作我们对要用到的小数链表(存放大于x值的链表)和大数链表分别定义他们各自的虚拟头结点
ListNode dummyHead1 = new ListNode(-1), dummyHead2 = new ListNode(-1);
ListNode cur1 = dummyHead1, cur2 = dummyHead2;
// 为防止链表丢失,我们不能直接使用虚拟头节点,
ListNode curp = pHead;
// curp指向原链表,我们接下来也是用curp来对原链表进行遍历操作的
while (curp != null) {
if (curp.val < x) {
cur1.next = curp;
// 当curp.val小于x时,给小数链表添加元素
cur1 = cur1.next;
}
else {
cur2.next = curp;
// 否则给大数链表增添元素
cur2 = cur2.next;
}
curp = curp.next;
// 更新curp对原来链表的指向,完成遍历操作
}
// 此时的cur1指向小数链表的最后一个结点,dummyHead2.next是大数链表的第一个结点
// 我们要把他们两个链接起来
cur1.next = dummyHead2.next;
cur2.next = null;
// cur2是大数链表的最后一个元素,指向空就行了
return dummyHead1.next;
// 返回小数链表的第一个元素
}
}
推荐阅读
- 一起刷好题|《力扣每日一题》—— 合并两个有序链表
- 一起刷好题|力扣每日一题(环形链表II)
- 力扣简单题目集|力扣——合并两个有序数组
- C语言|力扣每日一题——合并两个有序数组
- 点云数据处理|CloudCompare&PCL 泊松曲面重建算法
- 算法|机器学习 python 库_Python机器学习库
- 算法|2022数维杯全网思路+数据+代码
- Web服务教程入门介绍
- java/android 做题中整理的碎片小贴士