/*****************************************************
题目:输入一个链表,输出该链表倒数第K个节点。例如有一个
链表有6个节点,从头到尾他们的值依次是1,2,3,4,5,6.这个链
表倒数第3个节点是值为4的节点。
*****************************************************/
#include<stdio.h>
//链表节点结构
struct ListNode{
int m_nValue;
ListNode* m_pNext;
};
//创建链表节点
ListNode* createListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pNext = NULL;
return pNode;
}
//连接链表结点
void connectListNode(ListNode* pNode1, ListNode* pNode2)
{
if(!pNode1 || !pNode2)
return;
pNode1->m_pNext = pNode2;
}
//查找倒数第N个节点
ListNode* find_KthNode(ListNode* pHead, unsigned int k)
{
if(!pHead || k<0) //注意判断参数有效性,使代码鲁棒性健壮
return 0;
ListNode* pNode1 = pHead;
ListNode* pNode2 = pHead;
//找到离开始点后的第n-1个点
for(int i = 0; i<k-1; ++i)
{
if(pNode2->m_pNext)
pNode2 = pNode2->m_pNext;
else //排除链表节点数小于k的情况,使代码鲁棒性健壮
return NULL;
}
//两个链表指针都往后移动,直到第二个指针指向尾节点,
//则第一个指针就是倒数第k个节点
while(pNode2->m_pNext != NULL)
{
pNode1 = pNode1->m_pNext;
pNode2 = pNode2->m_pNext;
}
return pNode1;
}
void test()
{
ListNode* pNode1 = createListNode(1);
ListNode* pNode2 = createListNode(2);
ListNode* pNode3 = createListNode(3);
ListNode* pNode4 = createListNode(4);
ListNode* pNode5 = createListNode(5);
ListNode* pNode6 = createListNode(6);
connectListNode(pNode1,pNode2);
connectListNode(pNode2,pNode3);
connectListNode(pNode3,pNode4);
connectListNode(pNode4,pNode5);
connectListNode(pNode5,pNode6);
ListNode* pNode = find_KthNode(pNode1,3);
printf("%d\n",pNode->m_nValue);
}
int main()
{
test();
return 0;
}
==总结:
当我们用一个指针遍历链表不能解决问题的时候,可以尝试两个指针来遍历链表。
可以让其中一个指针遍历的速度快一些,或者让他先走几步。
相关题目:
1.求链表中间节点。
解决办法:使两个指针指向头结点,一个指针走一步,另一个走两个,
当速度快点都走到末尾,慢的就指向中间节点。
2.判断一个单项链表是否形成环形结构
定义两个指针指向头结点,一个走一步,另一个走两步。如果走得快的
跟上走的慢的,说明是环形链表;如果走的快的指针走到了末尾(m_pNext指向NULL)
都没有追上第一个指针,那么不是环形链表。
==参考剑指offer
分享到:
相关推荐
查找链表中倒数第K个节点,源代码验证通过,两种查找方法。
剑指 Offer 22. 链表中倒数第k个节点难度:简单输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数
Java输出链表倒数第k个节点 在Java编程中,输出链表倒数第k个节点是一个常见的问题,本文将为大家介绍三种不同的设计思路及代码示例,旨在帮助需要的朋友更好地理解和解决这个问题。 思路1:计算链表长度 第一种...
### 一次遍历找链表倒数第n个节点 在计算机科学中,链表是一种常用的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。有时候我们需要找到链表中的特定节点,例如倒数第n个节点。本篇文章将...
创建一个链表,编程实现查找它的倒数第k个节点
本题目的核心是查找链表中的倒数第k个节点,这是一个经典的链表问题,常见于面试和考研试题中。下面我们将深入探讨这个问题以及如何通过编程解决。 首先,链表是由一系列节点组成的数据结构,每个节点包含一个数据...
C CODE FOR :只遍历一遍找出单链表的倒数第K个节点
题目要求我们实现一个名为 `getKthFromEnd` 的函数,该函数接受两个参数:一个链表的头节点 `head` 和一个整数 `k`,返回链表中的倒数第 k 个节点。题目规定链表的倒数第 1 个节点是尾节点。 一种解决方法是遍历...
解决“链表中倒数第k个节点”这个问题的关键在于理解链表的结构以及如何有效地遍历它。这里我们将探讨双指针法,这是一种在链表问题中常用且高效的方法。 首先,我们要定义链表节点的结构。在Python中,我们可以...
本篇将详细讲解如何实现输出链表中倒数第k个节点的C语言程序。 首先,我们需要定义链表节点的结构体。在示例代码中,`Node` 结构体包含两个成员:`item` 存储数据元素,`next` 是指向下一个节点的指针。结构体初始...
在这个问题中,我们需要找到一个链表中倒数第k个节点。这个问题有多种解决方案,这里提供了两种方法:第一种是通过两次遍历链表,第二种是使用双指针一次遍历链表。 **方法一:两次遍历链表** 首先,我们来看第一...
"C++实现单链表删除倒数第k个节点的方法" 在C++编程中,单链表是一种常用的数据结构,删除单链表中的倒数第k个节点是一种常见的操作。本文将详细介绍C++实现单链表删除倒数第k个节点的方法,并结合实例形式分析了...
链表中倒数第k个节点.md
本题涉及的是如何在单链表中删除倒数第N个节点。这里提供了两种解决方案,分别称为解题思路一和解题思路二。 **解题思路一** 这个方法通过创建一个新的链表来实现。首先,遍历原链表计算其长度`count`。然后,根据...
剑指Offer(Python多种思路实现):链表中倒数第k个节点 面试22题: 题目:链表中倒数第k个节点 题:输入一个链表,输出该链表中倒数第k个结点。 解题思路一:为了实现只遍历链表一次就能找到倒数第k个节点,我们可以...
题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。 分析:使用两个指针,low,fast,先把fast的指针指向第k个元素,然后low和fast同时向后遍历,当fast遍历到结尾时,low...
在处理链表问题时,有时我们需要找到链表中的特定节点,比如倒数第k个节点。本题目的目标就是实现一个函数,给定一个链表和整数k,返回链表中倒数第k个节点。 链表通常由节点(ListNode)组成,每个节点包含一个值...
剑指 Offer 22. 链表中倒数第k个节点输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点
删除链表中的特定节点是一项常见的操作,特别是倒数第n个节点。在这个问题中,我们将使用快慢指针(又称龟兔赛跑算法)来解决这个问题。这是一种高效且简洁的方法,尤其适用于单链表。 首先,让我们理解什么是快慢...
剑指 Offer 22. 链表中倒数第k个节点难度:简单题目:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点