请选择 进入手机版 | 继续访问电脑版

876.链表的中间结点

[复制链接]
滚雪球少年 发表于 2021-1-2 19:44:05 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
第一次实验

  给定一个头结点为 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。链表为无头结点、单向、不循环。(由于涉及到结构体,所以写不了完整的测试代码,下面展示的代码为 LeetCode 中写的代码)(LeetCode链接)


  • 方法一:做两次循环,第一次计数有多少个节点,记为 count;第二次循环获取到第 count/2 + 1 个节点的数据;
  • 方法二:快慢指针,设置两个指针 fast、slow,初始时都指向首节点,然后 fast 每次走两步,slow 每次走一步,当 fast 走到链表末端,slow 正好指向中间的节点,这样一次循环就可以做到;
  1. struct ListNode* middleNode(struct ListNode* head){    //通例做法,两次循环    if(head->next == NULL){        return head;    }    struct ListNode* node = head;    //第一次循环计数count    int count = 0;    while(node){        node = node->next;        count++;    }    //找到中间位置    count = count/2 + 1;    while(count > 1){        head = head->next;        count--;    }    return head;    //快慢指针法    struct ListNode* fast = head;    struct ListNode* slow = head;    while(fast != NULL&&fast->next != NULL){        //快指针一次走两步,慢指针一次走一步        slow = slow->next;        fast = fast->next->next;    }    return slow;}
复制代码
博客园发表于 2020-12-11 14:43

来源:https://blog.csdn.net/Jokersorry/article/details/111558357
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )