一,题目:输入一个单向链表,输出该链表中倒数第k个结点,链表的倒数第0个结点为链表的尾指针。
二,分析:这是某一年的考研试题中,数据结构的一个题。题目本身难度不大。
三,思路:设置两个指针p1,p2;
p1=head; p2=head;
先让p2向前走k步,然后同时让p1,p2向后走。
当p2走到头的时候,p1所指的节点就是所求节点。
四,源码:
#include "stdio.h" #include "malloc.h" struct node { int data; node *next; }; node* fun(node *head,int k) { node *p1,*p2; p1 = p2 = head; for(int i=0;i<k;i++)//让第二个指针向后走k步 p2=p2->next; while(p2!=NULL) { p1=p1->next; p2=p2->next; } return p1; } int main() { int c; node *head,*p,*q; head = (node*)malloc(sizeof(node)); head->next = NULL; p = head; printf("请输入数字,以输出0为结尾\n"); scanf("%d",&c); while(c!=0) { q = (node*)malloc(sizeof(node)); q->data = c; q->next = NULL; p->next = q; p = p->next; scanf("%d",&c); //c = getchar(); } printf("-------输出第二个数--------\n"); printf("%d\n",fun(head,2)->data); //cout<<"---------------"<<endl; //cout<<fun(head,2)->data<<endl; return 0; }
您还没有登录,请您登录后再发表评论
当第一个指针到达链表尾部时,第二个指针所指向的节点即为倒数第k个节点。 #### 14. 二叉搜索树的转换 题目要求将一棵二叉搜索树转换为双向链表。 **解决方案**: 可以使用中序遍历的方式来进行转换。在中序遍历...
2. **找出单链表的倒数第4个元素**:可以通过双指针法,让一个指针先移动k-1步,然后两个指针同步移动,当先移动的指针到达链表末尾时,另一个指针所在位置就是倒数第k个元素。 3. **找出单链表的中间元素**:可以...
以2009年的真题为例,题目要求在不改变链表的前提下查找链表中倒数第k个位置上的结点,并输出该结点的data域的值。 - **算法设计思路**:使用两个指针p和q,初始时均指向头结点的下一个结点。先让p指针沿链表移动至...
#### 十三、O(1)时间删除链表节点 在给定链表中某个节点的指针的情况下,如何在O(1)时间内删除该节点?可以将当前节点的下一个节点复制到当前节点,然后删除下一个节点。 **示例:** ```java public void delete...
* 链表中倒数第 k 个节点 * 反转链表 * 合并两个排序的链表 * 树的子结构 * 二叉树的镜像 * 顺时针打印矩阵 * 定义一个栈,实现 min 函数 * 栈的压入弹出 * 从上往下打印二叉树 * 二叉搜索树的后序遍历 * 二叉树中和...
17. **删除倒数第k个节点**:给定一个整数k,删除链表的倒数第k个节点。 18. **链表的环的起始节点**:如果链表有环,找到环的起始节点。 19. **单链表的反转K个节点**:每次反转链表中的连续K个节点,保持其他...
5. 输出链表的倒数第K个元素:可以使用快慢指针,快指针先走K步,然后两者同步,快指针到达末尾时,慢指针即指向目标位置。 6. 栈的合法序列判断:栈的基本操作是入栈(I)和出栈(O)。合法序列必须满足任何时候栈...
1.3.2. 输入一个单向链表,输出该链表中倒数第 k 个结点............................. 44 1.3.3. 输入一个已经按升序排序过的数组和一个数字.................................... 46 1.3.4. 输入一颗二元查找树,...
首先让一个指针先移动k步,然后两个指针同步移动,当先移动的指针到达链表尾部时,另一个指针所指向的结点即为倒数第k个结点。 **(2)详细实现步骤:** 1. 初始化两个指针first和second,分别指向链表的头结点。 2...
找链表中倒数第K个节点.16.输出反转后的链表17.合并两个有序链表18.判断二叉树A中是否包含子树B.19.二叉树的镜像20.顺时针打印矩阵、21.包含min函数的栈.22.判断一个栈是否是另一个栈的弹出序列23.层序遍历二叉树。...
设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 查询链表的中间节点 一个每次走1步,一个每次走两步,走两步的遍历完,...
15. 找链表中倒数第K个节点:可以通过快慢指针的技巧,一个指针先走K步,然后两个指针同时移动,直到快指针到达终点。 16. 输出反转后的链表:需要考虑三个指针,分别记录当前节点、前一个节点和下一个节点,以便在...
找链表中倒数第K个节点 16. 输出反转后的链表 17. 合并两个有序链表 18. 判断二叉树A中是否包含子树B 19. 二叉树的镜像 20. 顺时针打印矩阵 21. 包含min函数的栈 22. 判断一个栈是否是另一个栈的弹出序列 23...
13. 链表中倒数第k个节点:找到链表中倒数第k个节点。 14. 反转链表:将链表的连接方向逆转。 15. 合并两个排序的链表:将两个已经排序好的链表合并成一个新的排序链表。 16. 树的子结构:判断一个树是否包含另一...
#### 三、(8分)采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,67,51 - **解析:** 使用哈希函数 H(k) = 3*...
- **问题描述**:给定一个链表,删除倒数第 n 个节点,并且返回链表的头结点。 - **解题思路**: - 使用双指针法,一个快指针先走 n 步,然后慢指针和快指针同时移动。 - 当快指针到达链表尾部时,慢指针恰好在待...
为了高效地解决这个问题,可以使用双指针技术,即设置两个指针,一个快指针和一个慢指针,让快指针先走k步,然后同时移动两个指针,当快指针到达链表尾部时,慢指针正好位于倒数第k个位置。 - **基本设计思想**:...
相关推荐
当第一个指针到达链表尾部时,第二个指针所指向的节点即为倒数第k个节点。 #### 14. 二叉搜索树的转换 题目要求将一棵二叉搜索树转换为双向链表。 **解决方案**: 可以使用中序遍历的方式来进行转换。在中序遍历...
2. **找出单链表的倒数第4个元素**:可以通过双指针法,让一个指针先移动k-1步,然后两个指针同步移动,当先移动的指针到达链表末尾时,另一个指针所在位置就是倒数第k个元素。 3. **找出单链表的中间元素**:可以...
以2009年的真题为例,题目要求在不改变链表的前提下查找链表中倒数第k个位置上的结点,并输出该结点的data域的值。 - **算法设计思路**:使用两个指针p和q,初始时均指向头结点的下一个结点。先让p指针沿链表移动至...
#### 十三、O(1)时间删除链表节点 在给定链表中某个节点的指针的情况下,如何在O(1)时间内删除该节点?可以将当前节点的下一个节点复制到当前节点,然后删除下一个节点。 **示例:** ```java public void delete...
* 链表中倒数第 k 个节点 * 反转链表 * 合并两个排序的链表 * 树的子结构 * 二叉树的镜像 * 顺时针打印矩阵 * 定义一个栈,实现 min 函数 * 栈的压入弹出 * 从上往下打印二叉树 * 二叉搜索树的后序遍历 * 二叉树中和...
17. **删除倒数第k个节点**:给定一个整数k,删除链表的倒数第k个节点。 18. **链表的环的起始节点**:如果链表有环,找到环的起始节点。 19. **单链表的反转K个节点**:每次反转链表中的连续K个节点,保持其他...
5. 输出链表的倒数第K个元素:可以使用快慢指针,快指针先走K步,然后两者同步,快指针到达末尾时,慢指针即指向目标位置。 6. 栈的合法序列判断:栈的基本操作是入栈(I)和出栈(O)。合法序列必须满足任何时候栈...
1.3.2. 输入一个单向链表,输出该链表中倒数第 k 个结点............................. 44 1.3.3. 输入一个已经按升序排序过的数组和一个数字.................................... 46 1.3.4. 输入一颗二元查找树,...
首先让一个指针先移动k步,然后两个指针同步移动,当先移动的指针到达链表尾部时,另一个指针所指向的结点即为倒数第k个结点。 **(2)详细实现步骤:** 1. 初始化两个指针first和second,分别指向链表的头结点。 2...
找链表中倒数第K个节点.16.输出反转后的链表17.合并两个有序链表18.判断二叉树A中是否包含子树B.19.二叉树的镜像20.顺时针打印矩阵、21.包含min函数的栈.22.判断一个栈是否是另一个栈的弹出序列23.层序遍历二叉树。...
设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 (-k+1+链表总数) % 链表总数 查询链表的中间节点 一个每次走1步,一个每次走两步,走两步的遍历完,...
15. 找链表中倒数第K个节点:可以通过快慢指针的技巧,一个指针先走K步,然后两个指针同时移动,直到快指针到达终点。 16. 输出反转后的链表:需要考虑三个指针,分别记录当前节点、前一个节点和下一个节点,以便在...
找链表中倒数第K个节点 16. 输出反转后的链表 17. 合并两个有序链表 18. 判断二叉树A中是否包含子树B 19. 二叉树的镜像 20. 顺时针打印矩阵 21. 包含min函数的栈 22. 判断一个栈是否是另一个栈的弹出序列 23...
13. 链表中倒数第k个节点:找到链表中倒数第k个节点。 14. 反转链表:将链表的连接方向逆转。 15. 合并两个排序的链表:将两个已经排序好的链表合并成一个新的排序链表。 16. 树的子结构:判断一个树是否包含另一...
#### 三、(8分)采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,67,51 - **解析:** 使用哈希函数 H(k) = 3*...
- **问题描述**:给定一个链表,删除倒数第 n 个节点,并且返回链表的头结点。 - **解题思路**: - 使用双指针法,一个快指针先走 n 步,然后慢指针和快指针同时移动。 - 当快指针到达链表尾部时,慢指针恰好在待...
为了高效地解决这个问题,可以使用双指针技术,即设置两个指针,一个快指针和一个慢指针,让快指针先走k步,然后同时移动两个指针,当快指针到达链表尾部时,慢指针正好位于倒数第k个位置。 - **基本设计思想**:...