hash rinetd 设计模式 mfc interface configuration ios4 requirejs android项目实战 ai视频教程下载 android项目开发 jq获取第一个子元素 java两个数组合并 arraylist删除指定元素 ajax里面可以嵌套ajax吗 idea全文搜索快捷键 mysql 导入数据 python计算器 python3网络编程 python教程推荐 python服务器开发 java数组追加 java输出数组 javastringbuilder java中random java语言入门 linux服务器登录 凯立德地图免费下载 脚本之家 神龙kms 网络是怎样连接的 js延迟加载的方式 ae脚本管理器 手机主题之家 lol体验服转换器 说话不算数的经典语句 给视频加字幕的软件 js保留两位小数 mysql使用教程 亚索刀光
当前位置: 首页 > 学习教程  > 编程语言

LeetCode题库中关于寻找链表的中间结点类似问题

2020/12/28 18:39:09 文章标签:

一.链表的中间结点 题目描述: 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 这是归属在一类快慢指针的解题类型中的题目。 //可以定义两个指针,一个每次走两步&#…

一.链表的中间结点

题目描述:
给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。
在这里插入图片描述
这是归属在一类快慢指针的解题类型中的题目。

//可以定义两个指针,一个每次走两步,一个每次只走一步,你就会发现,当快指针走到结尾的时候,慢指针刚好走到中间
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow =head;
     struct ListNode* fast =head;
     while(fast && fast->next) 
     //循环想的是结束的条件但是写的确实继续下去的条件,所以对于中间这个&&,是需要同时满足奇数个数组和偶数个数组的条件
     {
         slow = slow->next;
         fast = fast->next->next;
     }
     return slow;
}

在这里插入图片描述

二.

题目描述:

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

解题思路:定义两个指针,slow和fast,先让fast走k步,然两个指针一起走,那么他们之间的差值就一直是K,然后当fast为NULL的时候未结束的标志,此时的slow就是需要找的倒数第K个结点

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode* slow = pListHead,* fast = pListHead;
    //你这里的K值有可能比你链表本身的长度长,所以要保证其实有效的,
    //这一题最不好想到的就是这里。
        while(k--)
        {
            if(fast != NULL)
                fast = fast->next;
            else
                return NULL;
        }
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_550057.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?