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


    ced485cbb11e458d81a746890b32cf3f.gif 

    作者:渴望力量的土狗

    博客主页:渴望力量的土狗的博客主页

    专栏:手把手带你刷牛客

    工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网

    点击免费注册和我一起刷题吧

     

    目录

    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}。

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

    1. 示例1
    2. 输入:
    3. {1,2,3}
    4. 返回值:
    5. {3,2,1}
    6. 示例2
    7. 输入:
    8. {}
    9. 返回值:
    10. {}
    11. 说明:
    12. 空链表则输出空

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

      AC代码:

    1. /*
    2. public class ListNode {
    3. int val;
    4. ListNode next = null;
    5. ListNode(int val) {
    6. this.val = val;
    7. }
    8. }*/
    9. public class Solution {
    10. public ListNode ReverseList(ListNode head) {
    11. ListNode cur=head;
    12. ListNode pre=null;
    13. while(cur!=null){
    14. ListNode curNext=cur.next;
    15. cur.next=pre;
    16. pre=cur;
    17. cur=curNext;
    18. }
    19. return pre;
    20. }
    21. }

    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. 输入:
    3. {1,2},2
    4. 返回值:
    5. {2}

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

    AC代码:

    1. import java.util.*;
    2. /*
    3. * public class ListNode {
    4. * int val;
    5. * ListNode next = null;
    6. * }
    7. */
    8. public class Solution {
    9. /**
    10. *
    11. * @param head ListNode类
    12. * @param n int整型
    13. * @return ListNode类
    14. */
    15. public ListNode removeNthFromEnd (ListNode head, int n) {
    16. if(head==null){
    17. return null;
    18. }
    19. ListNode cur=head;
    20. ListNode pre =null;
    21. int newSize=size(head)-n;
    22. while(cur!=null&&newSize!=0){
    23. pre=cur;
    24. cur=cur.next;
    25. newSize--;
    26. }
    27. if(cur!=head){
    28. pre.next=cur.next;
    29. }else{
    30. head=cur.next;
    31. }
    32. return head;
    33. }
    34. public int size(ListNode head){
    35. int size=0;
    36. ListNode cur=head;
    37. while(cur!=null){
    38. cur=cur.next;
    39. size++;
    40. }
    41. return size;
    42. }
    43. }

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

    描述

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

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

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

    1. 示例1
    2. 输入:
    3. {1}
    4. 返回值:
    5. true
    6. 示例2
    7. 输入:
    8. {2,1}
    9. 返回值:
    10. false
    11. 说明:
    12. 2->1
    13. 示例3
    14. 输入:
    15. {1,2,2,1}
    16. 返回值:
    17. true
    18. 说明:
    19. 1->2->2->1

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

    AC代码:

    1. import java.util.*;
    2. /*
    3. * public class ListNode {
    4. * int val;
    5. * ListNode next = null;
    6. * }
    7. */
    8. public class Solution {
    9. /**
    10. *
    11. * @param head ListNode类 the head
    12. * @return bool布尔型
    13. */
    14. public boolean isPail (ListNode head) {
    15. // write code here
    16. if(head==null){
    17. return true;
    18. }
    19. if(head.next==null){
    20. return true;
    21. }
    22. ListNode slow=head;
    23. ListNode fast=head;
    24. while(fast!=null&&fast.next!=null){
    25. fast=fast.next.next;
    26. slow=slow.next;
    27. }
    28. ListNode cur=slow.next;
    29. while(cur!=null){
    30. ListNode curNext=cur.next;
    31. cur.next=slow;
    32. slow=cur;
    33. cur=curNext;
    34. }
    35. while(head!=slow){
    36. if(head.val!=slow.val){
    37. return false;
    38. }
    39. if(head.next==slow){
    40. return true;
    41. }
    42. head=head.next;
    43. slow=slow.next;
    44. }
    45. return true;
    46. }
    47. }

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

  • 相关阅读:
    用Pyhon写一款简单的益智类小游戏——2048
    Qt raise()问题
    【C++】继承 ⑫ ( 继承的二义性 | virtual 虚继承 )
    Jupyter Notebook又一利器nbterm,在终端玩Python!
    手机爬虫用Appium详细教程:利用Python控制移动App进行自动化抓取数据
    自动阅卷的原理很简单的,用python来简单解释一下工作原理❤
    【如何成为学习高手】学习是有方法的,按照正确的方法练习,每个人都可以成为学霸
    186页13万字智慧能源大数据分析平台建设方案
    Mysql三种日志(binlog,redolog,undolog)的作用和区别
    大数据之路读书笔记-01总述
  • 原文地址:https://blog.csdn.net/m0_67995737/article/details/127698050