求链表中第i个结点的指针。
时间: 2024-04-09 08:28:39 浏览: 15
对于链表中的第i个节点,我们需要遍历链表,找到对应位置的节点。下面是一种实现方法:
1. 定义一个指针`current`,指向链表的头节点。
2. 使用一个计数器`count`,初始化为1。
3. 在一个循环中,遍历链表,每次将`current`指针移动到下一个节点。
4. 在循环中,检查`count`是否等于目标位置i,如果是,则返回`current`指针。
5. 如果循环结束后仍然没有找到第i个节点,则表示链表长度小于i,返回空指针。
下面是一个示例的C++代码实现:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* getIthNode(ListNode* head, int i) {
ListNode* current = head;
int count = 1;
while (current != NULL) {
if (count == i) {
return current;
}
current = current->next;
count++;
}
return NULL; // 链表长度小于i,返回空指针
}
```
请注意,这只是一种简单的实现方法。在实际应用中,可能需要考虑更多的边界情况和错误处理。
相关问题
求单项链表中第i个结点的指针(函数),若不存在,则返回NULL
以下是求单项链表中第i个结点的指针的函数实现(C语言):
```
struct ListNode* getIthNode(struct ListNode* head, int i) {
if (head == NULL || i < 1) { // 判断链表头指针和i的合法性
return NULL;
}
struct ListNode* cur = head;
while (i > 1 && cur != NULL) { // 找到第i个结点的前一个结点
cur = cur->next;
i--;
}
return cur; // 返回第i个结点的指针,如果不存在,则返回NULL
}
```
使用方法如下:
1. 定义链表结点的结构体:
```
struct ListNode {
int val;
struct ListNode *next;
};
```
2. 创建单项链表并初始化:
```
struct ListNode* head = malloc(sizeof(struct ListNode)); // 创建头结点
head->val = 1; // 初始化头结点的值
head->next = NULL; // 初始化头结点的指针
struct ListNode* cur = head; // 创建指针cur指向头结点
for (int i = 2; i <= n; i++) { // 创建n个结点,并连接成链表
struct ListNode* node = malloc(sizeof(struct ListNode));
node->val = i;
node->next = NULL;
cur->next = node;
cur = node;
}
```
3. 调用函数获取第i个结点的指针:
```
struct ListNode* ithNode = getIthNode(head, i);
if (ithNode == NULL) {
printf("第%d个结点不存在\n", i);
} else {
printf("第%d个结点的值为%d\n", i, ithNode->val);
}
```
删除线性链表倒数第i个结点
可以使用双指针法来解决这个问题。首先,让一个指针从链表的头部开始移动 i 个位置,然后让另一个指针从链表的头部开始移动,直到第一个指针到达链表的末尾。此时,第二个指针所指向的结点就是倒数第 i 个结点。然后,我们可以将该结点从链表中删除即可。
以下是示例代码:
```
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p = head, *q = head;
for (int i = 0; i < n; i++) {
p = p->next;
}
if (!p) {
return head->next;
}
while (p->next) {
p = p->next;
q = q->next;
}
q->next = q->next->next;
return head;
}
```
这段代码实现了删除链表倒数第 n 个结点的功能。如果链表长度小于 n,直接返回 head->next 即可。