剑指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)
blank

相关推荐

  • 二进制加减运算

    二进制加减运算二进制加法原则是:2个1相加等于2就要向前给1,下面得算为0,相当于十进制1+9=10向前给1,下面得算为0,因为二进制只有0和1,所以1加1等于2多了一个1就要往前送。二进制减法原则是:0减1不够,就向前借2减11、加法实例11001100+0000110011001100+00001100——————11011000首先右边两个0相加为0,右3位1+1=2就要给前面1个1,下面得数为0,右4位因为前面给了一个1,所以现在就是1+1+1=3,把2向前给1,然后3..

  • 密钥库文件不存在: debug.keystore

    密钥库文件不存在: debug.keystore

  • Intellij Idea 主题下载(Eclectide Monokai)

    Intellij Idea 主题下载(Eclectide Monokai)从国外大神的博客上找的一个很棒的主题EclectideMonoka,感觉是在Durcula上做了很多优化,是黑色主题的升级版,通过一周的使用感觉非常爽,对方法、变量的高亮以及选中的显示等等色彩搭配挺好,分享一下

  • Cocos2D-X学习笔记 3 从一个场景切换到还有一个场景

    Cocos2D-X学习笔记 3 从一个场景切换到还有一个场景

  • 《前端运维》一、Linux基础–09常用软件安装

    一、软件包管理RPM是RedHatPackageManager(RedHat软件包管理工具)类似Windows里面的"添加/删除程序"。软件包有几种类型,我们一起来看下:源

  • Linux抓包命令_怎么使用wireshark抓包

    Linux抓包命令_怎么使用wireshark抓包Wireshark是一款图形化的抓包软件,在LInux和Windows下都可以下载。用命令安装wireshark相关软件包命令:查看安装wireshark产生了哪些文件直接通过命令打开或者是图形化页面点开就好点击InterfaceList,就可以看到接口列表,选择需要抓哪个网卡的包这里我选择ens33网卡,点击start开始抓包我们ping我们的主机地址,看看抓包情况ping工具使用的就是协议,ICMP是IP协议的附属协议。IP层用它来与其他主机或路由器交换错误报文和其他重要信息。它主要是

发表回复

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

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