《牛客每日一题》链表分割、输出链表的倒数第k个结点

约定不等于承诺〃 2024-04-23 15:37 64阅读 0赞

> ✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿
> 
> ?博客首页：[是小鱼儿哈][Link 1]
> 
> ?系列专栏：[一起刷好题][Link 2]
> 
> ?每日一句**：努力不是重点，常态化才是关键。真正努力的人，能随时进入任何角色，在过程中找到感觉和快乐。**
> 
> ?博主也在学习阶段，如发现问题请告知，非常感谢?

**目录**

一、输出链表的倒数第k个结点

二、链表分割

--------------------

## **一、输出链表的倒数第k个结点**  ##

>  **题目链接：[输出链表的倒数第k个结点][k]**

![f3adbae710804111af71ee96987668ba.png][]

**?思路一：通过遍历链表，求得链表的长度，然后求得返回的是正数的第一个结点**

>     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 > 链表的长度**

--------------------

## 二、链表分割 ##

> **题目链接** 
> 
> [链表分割——牛客][Link 3]

![21dadfac010343b4b77f1fed686d72e7.png][]

?**思路：设置两个链表头，遍历原链表，一个追加小数链表，一个追加大数链表，最后将小数链表粘到大数链表前边即为结果。**

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; // 返回小数链表的第一个元素
        }
    }

[Link 1]: https://blog.csdn.net/weixin_61061381?type=blog
[Link 2]: https://blog.csdn.net/weixin_61061381/category_11776133.html
[k]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[f3adbae710804111af71ee96987668ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2f2479c3c916440e9299c9e2acec5d7b.png
[Link 3]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[21dadfac010343b4b77f1fed686d72e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/205f66f020284c1eaf926c71ea22eff2.png