单链表查找第i个结点
时间: 2023-12-23 17:03:29 浏览: 92
好的,针对您的问题,下面是单链表查找第i个结点的代码示例(假设链表的头结点为head):
```python
def find_node(head, i):
"""
查找单链表中第i个结点
"""
if i < 1:
return None
node = head.next
j = 1
while node and j < i:
node = node.next
j += 1
if j == i and node:
return node
else:
return None
```
实现原理是从链表的头结点开始遍历,依次访问每个结点,直到找到第i个结点或者遍历到链表的末尾。
需要注意的是,链表的下标从1开始,而不是从0开始。另外,如果i小于1或者大于链表的长度,都应该返回None。
相关问题
查找单链表倒数第k个结点(***
要查找单链表倒数第k个结点,可以采用双指针的方法。
具体操作如下:
1. 定义两个指针p1和p2,初始都指向头结点。
2. 让p1指针先移动k个结点。
3. 然后同时移动p1和p2指针,直到p1指针到达链表末尾。
4. 此时p2指针所指的结点就是倒数第k个结点。
代码如下:
```
struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k)
{
if(pListHead == NULL || k == 0)
return NULL;
ListNode* p1 = pListHead;
ListNode* p2 = pListHead;
// p1指针先移动k个结点
for(unsigned int i=0; i<k-1; ++i)
{
if(p1->next != NULL)
p1 = p1->next;
else
return NULL; // 如果链表长度小于k,返回NULL
}
// p1和p2指针同时移动
while(p1->next != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
```
在带头结点单链表中查找第i个结点,完成函数 node *find(node *head, int i)的功能。
好的,这是一个比较简单的链表问题。以下是代码实现:
```c++
typedef struct node{
int data;
struct node *next;
}node;
node *find(node *head, int i){
if(head == NULL || i <= 0) // 非法输入
return NULL;
node *p = head->next; // 从第一个结点开始
int j = 1;
while(p != NULL && j < i){ // 遍历链表
p = p->next;
j++;
}
if(j == i) // 找到第i个结点
return p;
else // 链表中没有第i个结点
return NULL;
}
```
函数的参数是一个带头结点的链表头指针和要查找的结点位置i。首先需要判断输入的参数是否合法,即链表是否为空或者i是否小于等于0,如果是则直接返回NULL。接着从第一个结点开始遍历链表,每遍历一个结点就将计数器j加1,直到找到第i个结点或者遍历到链表末尾。如果找到了第i个结点,则返回该结点的指针,否则返回NULL。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)