【牛客】链表中倒数第K个节点, 链表分割, 链表的回文结构

╰半橙微兮° 2023-09-26 10:08 21阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  1. 链表中倒数第K个节点
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  2. 链表分割(CM11)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  3. 链表的回文结构(OR36)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：

## 1. 链表中倒数第K个节点 ##

### 题目描述: ###

**描述** :

输入一个链表，输出该链表中倒数第k个结点。

**示例1** :

输入：1,\{1,2,3,4,5\}

返回值：\{5\}

**链接：**[点这里][Link 1]  
**来源：** 牛客网

### 解题思路： ###

快慢指针实现 , 定义两个引用变量 fast(快) 和 slow(慢) , 先让 fast 走k-1步 , 走完之后此时 fast 和 slow 再同时走 , 当 fast 走到最后一个节点时 , show 指向的就是 倒数第 k 个节点

![img][]

### 代码实现： ###

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        public ListNode FindKthToTail(ListNode head,int k) {
        
             if(k <= 0 || head == null) {
        
                 return null;
             }
             ListNode fast = head;
             ListNode slow = head;
             //先让fast走k-1步
             while(k-1 != 0) {
        
                 fast = fast.next;
                 if(fast == null) {
        
                     return null;
                 }
                 k--;
             }
             while(fast.next != null) {
        
                 fast = fast.next;
                 slow = slow.next;
             }
             return slow;
        }
    }

### 提交结果： ###

![img][img 1]

## 2. 链表分割(CM11) ##

### 题目描述: ###

**描述** :

现有一链表的头指针 ListNode\* **pHead**，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

**链接：**[点这里][Link 2]  
**来源：** 牛客网

### 解题思路： ###

从前到后逐个按顺序去遍历链表节点 , 将小于x的元素逐个按顺序插入到一个新的链表中 , 同样的将大于x的元素逐个按顺序插入到一个新的链表中 ; 最后将小于x的链表的尾节点和大于x的链表的头节点连接起来组成一个新的链表 , 返回头节点即可 ;

那么如何去实现这两个链表呢 , 我们可以声明两个引用as 和 ae , 用来维护比x大的链表 ; 再声明bs和be来维护比x小的链表 ;

代码中还有几点细节需要注意 , 大于x的链表的最后一个节点相当于合并后链表的尾节点 , 要注意此时尾节点的next不一定为null , 需要去判断并置空 ; 将两个链表合并前要去判断较小的链表是不是空链表 , 是的话直接返回bs .

![img][img 2]

### 代码实现： ###

import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Partition {
        
        public ListNode partition(ListNode pHead, int x) {
        
           ListNode cur = pHead;
           //指向比x小的部分
           ListNode bs = null;
           ListNode be = null;
           //指向比x大的部分
           ListNode as = null;
           ListNode ae = null;
           //遍历整个链表
           while(cur != null) {
        
               if(cur.val < x) {
        
                   //第一次插入节点
                   if(bs == null) {
        
                       bs = cur;
                       be = cur;
                   }else {
        
                       //不是第一次插入节点
                       be.next = cur;
                       be = be.next;
                   }
               }else {
        
                   if(as == null) {
        
                       as = cur;
                       ae = cur;
                   }else {
        
                       ae.next = cur;
                       ae = ae.next;
                   }
               }
               cur = cur.next;
           }
           //判断较小部分是不是空链表
           if(be == null) {
        
               return as;
           }
           //将两段链表连接起来
           be.next = as;
           //将尾节点的next设置为null
           if(as != null) {
        
               ae.next = null;
           }
           return bs;
        }
    }

### 提交结果： ###

![img][img 3]

## 3. 链表的回文结构(OR36) ##

### 题目描述: ###

**描述** :

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针**A**，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

**测试样例**：

1->2->2->1

返回：true

**链接：**[点这里][Link 3]  
**来源：** 牛客网

### 解题思路： ###

判断链表是不是回文结构 , 只需要两个指针 , 一个从前往后 , 另一个从后往前 , 判断每一对元素是不是相等 ;但是单链表只支持从前往后遍历 , 实现不了从后往前的 ; 由此我们就想怎么才能实现将后半段链表元素从后往前遍历呢?

所以这里可以去实现将链表的后半段节点反转(反转单链表) , 此时上面的想法就可以实现了 , 后半段的反转需要先找到中间节点(利用快慢指针去实现) ;

要实现这个过程还有很多细节需要注意 , 具体看下面给出的代码 .

![img][img 4]

### 代码实现： ###

import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class PalindromeList {
        
        public boolean chkPalindrome(ListNode head) {
        
            //判断是否为空列表
            if(head == null) {
        
                return false;
            }
            //只有一个节点时
            if(head.next == null){
        
                return true;
            }
            //找到中间节点
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
            //将show后半段链表反转
            ListNode cur = slow.next;
            while(cur != null) {
        
                //先记录cur的下一个节点位置，否则再反转后会失联
                ListNode curNext = cur.next;
                //更改指向
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //判断回文，此时show相对于原链表在最后一个位置
            while(head != slow) {
        
                if(head.val != slow.val) {
        
                    return false;
                }
                //处理偶数情况
                if(head.next == slow) {
        
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
    
            return true;
        }
    }

### 提交结果： ###

![img][img 5]

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11990219.html?spm=1001.2014.3001.5482
[Link 1]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking0ed8e465a84821c8f3970b7b5
[img]: https://img-blog.csdnimg.cn/img_convert/84ceb5d17819f212ef7c89e0fbf40762.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/22ba7713e620d13f6d3ee7e33d10f78b.png
[Link 2]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[img 2]: https://img-blog.csdnimg.cn/img_convert/c8a75a4d50996a1bb2a954fe3b18c50f.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/1d9a84eb1979828bf7f583c5c0a3008b.png
[Link 3]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[img 4]: https://img-blog.csdnimg.cn/img_convert/65c323515abf757965758d0a36cfdf6a.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/d2609d711a9173c08490111c72447a90.png