浅刷牛客链表题，逐步深入链表，理解链表

柔情只为你懂 2024-04-01 14:53 30阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[手把手带你刷牛客][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![f4848c359919444a8f442872d746533b.png][]

**目录**

1、反转链表

2、删除链表的倒数第n个节点

3、判断一个链表是否为回文结构

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

## 1、反转链表 ##

**描述**

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度O(n) 。

如当输入链表\{1,2,3\}时，

经反转后，原链表变为\{3,2,1\}，所以对应的输出为\{3,2,1\}。

以上转换过程如下图所示：

![c59dd55c575b4367adf19c1f3abf3376.png][]

示例1
    输入：
    {1,2,3}
    返回值：
    {3,2,1}
    
    
    
    示例2
    输入：
    {}
    返回值：
    {}
    说明：
    空链表则输出空

思路描述：为了反转链表，简单一点说就是把结点的next值进行一个修改，如果我们用cur来记录当前的结点，那么在修改指向的时候，我们需要知道它的前一个结点(pre)和后一个结点(curNext)，因为一旦指向修改完成后，后面的结点就找不到了，所以我们需要记录一下。所以我们首先记录一下当前结点的下一个结点，然后把当前结点cur的next指向pre,让pre后移，也就是pre=cur；然后让cur指向记录的curNext即可，直至遍历完整个链表。

AC代码：

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode ReverseList(ListNode head) {
    
            ListNode cur=head;
    
            ListNode pre=null;
    
            while(cur!=null){
                ListNode curNext=cur.next;
                cur.next=pre;
                pre=cur;
                cur=curNext;
            }
    
            return pre;
    
        }
    }

## 2、删除链表的倒数第n个节点 ##

**描述**

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针  
例如，给出的链表为: 1→2→3→4→5, n=2.  
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.

数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度O(n)  
备注：题目保证 n 一定是有效的

示例1
    输入：
    {1,2},2    
    
    返回值：
    {2}

思路描述：首先要判空，否则就没有必要进行下去了。删除链表中结点的操作就比较简单，直接让该结点的前一个结点的next指向该结点的后一个结点即可。本题的关键在于如何找到这个结点，由于是倒数的，所以我们要算出该链表的长度，就写个size函数即可。然后把倒数转化为正着数即可，定义一个newSize=size(head)- n;即可得到正着的结点位置，然后进行删除操作即可！

AC代码：

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param head ListNode类 
         * @param n int整型 
         * @return ListNode类
         */
        public ListNode removeNthFromEnd (ListNode head, int n) {
            if(head==null){
                return null;
            }
            ListNode cur=head;
            ListNode pre =null;
            int newSize=size(head)-n;
            while(cur!=null&&newSize!=0){
                pre=cur;
                cur=cur.next;
                newSize--;
            }
            if(cur!=head){
                pre.next=cur.next;
            }else{
                head=cur.next;
            }
    
    
            return head;
    
        }
        public int size(ListNode head){
            int size=0;
            ListNode cur=head;
            while(cur!=null){
                cur=cur.next;
                size++;
            }
            return size;
        }
    }

## 3、判断一个链表是否为回文结构 ##

**描述**

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0≤n≤10^5，链表中每个节点的值满足 ∣val∣≤10^7

示例1
    输入：
    {1}
    
    返回值：
    true
    
    示例2
    输入:
    {2,1}
    
    返回值：
    false
    
    说明：
    2->1     
    示例3
    输入：
    {1,2,2,1}
    
    返回值：
    true
    
    说明：
    1->2->2->1

思路描述：回文数我们见的多了，对于链表，我们想知道是不是回文数，经常使用双指针来解决。这题的关键在于找到中间结点，然后将中间结点后面的结点进行反转，反转完了之后分别从两端开始进行比较，直到出现不相等为止，如果没有不相等的，就是回文，有不相等的就不是回文。主要思想就是定义一个快指针，一个慢指针，快的一次走两步，慢的一次走一步，当快的走到链表的尾结点的时候，慢的就是中间结点的位置，然后把它后面的结点进行反转，上面说过怎么反转了，最后，从两端开始比较即可！

AC代码：

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param head ListNode类 the head
         * @return bool布尔型
         */
        public boolean isPail (ListNode head) {
            // write code here
              if(head==null){
                return true;
            }
            if(head.next==null){
                return true;
            }
           
    
            ListNode slow=head;
            ListNode fast=head;
    
            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;
            }
    
            while(head!=slow){
                if(head.val!=slow.val){
                    return false;
                }
                if(head.next==slow){
                    return true;
                }
                head=head.next;
                slow=slow.next;
            }
            return true;
        }
    }

![73830d8121de4c2391cf57a822dfe60a.png][]

>  “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0c2893d69d154059914c7774181fbf33.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_11980422.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[f4848c359919444a8f442872d746533b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6cc5a8a8fe1c490497a9b411927fe994.png
[c59dd55c575b4367adf19c1f3abf3376.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4502b7dce0c64b2aa21f1682d8b02183.png
[73830d8121de4c2391cf57a822dfe60a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bbaccfd9ba104ec28f6c30515e54d22c.png