热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

C语言:【单链表】查找单链表的倒数第k个节点,要求只能遍历一次

#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefintDataType;ty
#include
#include
#include

typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;
}SListNode;

SListNode* BuyNode(DataType x)
{
    SListNode* next = (SListNode*)malloc(sizeof(SListNode));
    next->data = x;
    next->next = NULL;
    return next;
}

void PushBack(SListNode* & ppHead, DataType x)
{
    if (ppHead == NULL)
    {
        ppHead = BuyNode(x);
    }
    else
    {
        SListNode* tail = ppHead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = BuyNode(x);
    }
}
//查找单链表的倒数第k个节点,要求只能遍历一次
SListNode* FindLastKMiddle(SListNode* ppHead,DataType k)
{
    SListNode* slow = ppHead;
    SListNode* fast = ppHead;
    while (fast !=NULL && k--)
    {
        fast = fast->next;
    }
    if (k > 0)
    {
        return NULL;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
void PrintSNodeList(SListNode* ppHead)
{
    while (ppHead)
    {
        printf("%d->", ppHead->data);
        ppHead = ppHead->next;
    }
    printf("\n");
}

void Test3()
{
    SListNode* List = NULL;
    PushBack(List, 1);
    PushBack(List, 2);
    PushBack(List, 3);
    PushBack(List, 4);
    PushBack(List, 5);
    PrintSNodeList(List);
    SListNode *ret = FindLastKMiddle(List, 4);
    if (ret == NULL)
    {
        printf("该值不存在!\n");
    }
    else
    {
        printf("%d ", ret->data);
    }
}

int main()
{
    Test3();
    system("pause");
    return 0;
}



推荐阅读
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • c语言\n不换行,c语言printf不换行
    本文目录一览:1、C语言不换行输入2、c语言的 ... [详细]
  • 李逍遥寻找仙药的迷阵之旅
    本文讲述了少年李逍遥为了救治婶婶的病情,前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵,有些方格内有怪物,有些方格是安全的。李逍遥需要避开有怪物的方格,并经过最少的方格,找到仙药。在寻找的过程中,他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]
  • 本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes,通过状压和spfa算法解决了这个问题。给定一个有向图,求在不超过m步的情况下,能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]
  • STL迭代器的种类及其功能介绍
    本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系,并详细描述了各个迭代器的功能和使用方法。其中,输入迭代器用于从容器中读取元素,输出迭代器用于向容器中写入元素,正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]
  • 本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法,并提供了一个范例。通过宏定义的方式,可以方便地处理不定参数的情况。文章中给出了具体的代码实现,并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说,是一个很有用的参考资料。 ... [详细]
  • 本文介绍了为什么要使用多进程处理TCP服务端,多进程的好处包括可靠性高和处理大量数据时速度快。然而,多进程不能共享进程空间,因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码,并对代码进行了详细注释。 ... [详细]
  • 本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体,实现了入队和出队操作,并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • OO第一单元自白:简单多项式导函数的设计与bug分析
    本文介绍了作者在学习OO的第一次作业中所遇到的问题及其解决方案。作者通过建立Multinomial和Monomial两个类来实现多项式和单项式,并通过append方法将单项式组合为多项式,并在此过程中合并同类项。作者还介绍了单项式和多项式的求导方法,并解释了如何利用正则表达式提取各个单项式并进行求导。同时,作者还对自己在输入合法性判断上的不足进行了bug分析,指出了自己在处理指数情况时出现的问题,并总结了被hack的原因。 ... [详细]
  • 如何在跨函数中使用内存?
    本文介绍了在跨函数中使用内存的方法,包括使用指针变量、动态分配内存和静态分配内存的区别。通过示例代码说明了如何正确地在不同函数中使用内存,并提醒程序员在使用动态分配内存时要手动释放内存,以防止内存泄漏。 ... [详细]
  • 本文介绍了一道经典的状态压缩题目——关灯问题2,并提供了解决该问题的算法思路。通过使用二进制表示灯的状态,并枚举所有可能的状态,可以求解出最少按按钮的次数,从而将所有灯关掉。本文还对状压和位运算进行了解释,并指出了该方法的适用性和局限性。 ... [详细]
  • 本文介绍了一种划分和计数油田地块的方法。根据给定的条件,通过遍历和DFS算法,将符合条件的地块标记为不符合条件的地块,并进行计数。同时,还介绍了如何判断点是否在给定范围内的方法。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • Redis底层数据结构之压缩列表的介绍及实现原理
    本文介绍了Redis底层数据结构之压缩列表的概念、实现原理以及使用场景。压缩列表是Redis为了节约内存而开发的一种顺序数据结构,由特殊编码的连续内存块组成。文章详细解释了压缩列表的构成和各个属性的含义,以及如何通过指针来计算表尾节点的地址。压缩列表适用于列表键和哈希键中只包含少量小整数值和短字符串的情况。通过使用压缩列表,可以有效减少内存占用,提升Redis的性能。 ... [详细]
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
author-avatar
安安ahui
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有