剑指Offer面试题:12.链表的倒数第K个结点

一题目:链表的倒数第K个结点二解题思路抛开常规解法,采用只遍历一次就能找到倒数第k个结点,可以定义两个指针:(1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;(2)从

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

剑指Offer面试题:12.链表的倒数第K个结点此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

一 题目:链表的倒数第K个结点

题目:输入一个链表,输出该链表中倒数第k个结点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾结点是倒数第1个结点。例如一个链表有6个结点,从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

二 解题思路

  抛开常规解法,采用只遍历一次就能找到倒数第k个结点,可以定义两个指针:

  (1)第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动

  (2)从第k步开始,第二个指针也开始从链表的头指针开始遍历

  (3)由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点

三 代码实现

template <typename T>
struct Node
{
public:
    T data;
    Node *pNext;
};

template <typename T>
class ListEx
{
private:
    Node<T> *m_pHead;
    Node<T> *m_pTail;
public:
    ListEx()
    {
        m_pTail = m_pHead = NULL;
    }
    ~ListEx()
    {
        Node<T> *pTemp = NULL;
        Node<T> *pNode = m_pHead;
        while (pNode)
        {
            pTemp = pNode;
            pNode = pNode->pNext;
            delete pTemp;
        }

        m_pHead = m_pTail = NULL;
    }
    void add(T data)
    {
        Node<T> *pNode = new Node<T>;
        pNode->data = data;
        pNode->pNext = NULL;

        if (m_pHead == NULL)
        {
            m_pTail = m_pHead = pNode;
        }

        Node<T>* pTemp = m_pTail;
        pTemp->pNext = pNode;
        m_pTail = pNode;
    }

    Node<T> *GetListHead()
    {
        return m_pHead;
    }
};

// 链表的倒数第k个结点,注意倒数从1开始
template <typename T>
Node<T>* FindKthToTail(Node<T> *pNode, int k)
{
    // k必须不大于Node的结点数目
    if (!pNode || k < 0) return NULL;
    Node<T> *p1 = pNode;
    Node<T> *p2 = pNode;

    int nIndex = 0;
    bool bStart = false;
    int nFalg = 0;
    while (NULL != p2->pNext)
    {
        if (nIndex == k-1)
        {
            bStart = true;
        }
        if (bStart)
        {
            p1 = p1->pNext;
        }

        p2 = p2->pNext;
        nIndex ++;
    }
    return p1;
}

void main()
{
    ListEx<int> *pList= new ListEx<int>();
    pList->add(1);
    pList->add(2);
    pList->add(3);
    pList->add(4);
    pList->add(5);
    pList->add(6);
    pList->add(7);

    Node<int> *pHead = pList->GetListHead();
    Node<int> *pNode = FindKthToTail(pHead, 2);
    cout << pNode->data <<endl;
    pNode = FindKthToTail(pHead, 1);
    cout << pNode->data <<endl;
    pNode = FindKthToTail(pHead, 7);
    cout << pNode->data <<endl;

    delete pList;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120162.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vue分页列表[通俗易懂]

    vue分页列表[通俗易懂]html部分css部分js部分

  • Ubuntu搭建饥荒服务器教程

    Ubuntu搭建饥荒服务器教程安装编译环境Ubuntu/Debian64-Bitsudoapt-getinstalllib32gcc1screenRedHat/CentOS32-Bityum-yinstallglibclibstdc++screenlibcurlRedHat/CentOS64-Bityum-yinstallglibc.i686libstdc++.i686screenlibcurl.i686yuminstallglibc.i686下载steamCMDwget

  • getchar的用法举例_getchar能输入字符串吗

    getchar的用法举例_getchar能输入字符串吗c语言getchar的用法:1.从缓冲区读走一个字符,相当于清除缓冲区2.前面的scanf()在读取输入时会在缓冲区中留下一个字符’\n’(输入完s[i]的值后按回车键所致),所以如果不在此加一个getchar()把这个回车符取走的话,gets()就不会等待从键盘键入字符,而是会直接取走这个“无用的”回车符,从而导致读取有误3.getchar()是在输入缓冲区…

    2022年10月19日
  • 【转载】Win10强制删除文件夹

    【转载】Win10强制删除文件夹目前比较主流的Windows系统中,我们常常会遇到要对文件以及文件夹进行整理的时候,偶尔会遇到这种奇葩的问题:删除一个文件夹的时候吧,这个文件提示需要提供管理权限,问你是否继续。当点击了那个带盾牌的(就是赋予管理权限)的那个Button之后,仍然提示需要权限……简直不讲道理。因为这个东西是偶然出现的,所以这里留几个解决方法备用。1.重启重启能解决99%的问题!!!亘古不变的真理!2.修改权限右键要删除的文件,选择属性——在属性页面可以看到上方有安全权限,点击之后选择一个.

  • arping 命令解析

    arping 命令解析一、介绍ARP协议是“AddressResolutionProtocol”(地址解析协议)的缩写。在同一以太网中,通过地址解析协议,源主机可以通过目的主机的IP地址获得目的主机的MAC地址。arping程序就是完成上述过程的程序。arping,用来向局域网内的其它主机发送ARP请求的指令,它可以用来测试局域网内的某个IP是否已被使用。 二、指令格式如下:arping[-AbDfhqUV][…

  • CentOS8快速部署轻量级自动化运维平台Spug

    CentOS8快速部署轻量级自动化运维平台SpugSpug面向中小型企业设计的轻量级无Agent的自动化运维平台,整合了主机管理、主机批量执行、主机在线终端、文件在线上传下载、应用发布部署、在线任务计划、配置中心、监控、报警等一系列功能。Spug的特性批量执行:主机命令在线批量执行在线终端:主机支持浏览器在线终端登录文件管理:主机文件在线上传下载任务计划:灵活的在线任务计划发布部署:支持自定义发布部署流程配置中心:支持KV、文本、json等格式的配置监控中心:支持站点、端口、进程、自定义等监控报警中心:支持短信、

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号