c语言求倒数第n个节点
时间: 2023-12-13 10:04:48 浏览: 37
假设我们有一个单向链表,要求找到倒数第 n 个节点,可以使用双指针算法来实现。
具体做法是,定义两个指针 p1 和 p2,初始时都指向链表头节点。然后,将 p2 向前移动 n 个节点,此时 p1 和 p2 之间的距离就是 n。接着,同时将 p1 和 p2 向前移动,直到 p2 指向链表尾节点。此时,p1 就指向了倒数第 n 个节点。
具体代码如下:
```c
struct ListNode* getNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p1 = head, *p2 = head;
// 将 p2 向前移动 n 个节点
for (int i = 0; i < n; i++) {
p2 = p2->next;
}
// 同时将 p1 和 p2 向前移动,直到 p2 指向链表尾节点
while (p2 != NULL) {
p1 = p1->next;
p2 = p2->next;
}
// p1 指向倒数第 n 个节点
return p1;
}
```
需要注意的是,如果链表长度小于 n,那么上述代码会返回空指针。如果需要在这种情况下返回错误代码或者抛出异常,可以在代码中进行相应的处理。
相关问题
C语言输入一个链表,输出这个链表的倒数第K个节点
在C语言中,要输入一个链表并输出其倒数第K个节点,首先你需要创建一个链表结构,然后实现一个方法来遍历链表,找到倒数第K个节点。这里是一个简单的步骤说明:
1. **定义链表结构**:
假设链表节点定义如下:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
```
2. **输入链表**:
创建一个函数来接收用户输入或已存在的链表节点,并构建链表:
```c
void inputList(Node** head, int K) {
Node* current = *head;
int k = 0;
// 输入节点数据和添加到链表
while (current != NULL) {
// 用户输入或从已有的链表获取数据
// ...
current = current->next;
k++;
}
// 链表长度至少是K+1(因为从头开始计数)
if (k < K) {
printf("链表太短,无法找到倒数第K个节点");
return;
}
}
```
3. **遍历链表找到倒数第K个节点**:
使用两个指针,快慢指针,快指针每次前进两步,慢指针每次前进一步。当快指针到达链表尾部时,慢指针指向的就是倒数第K个节点:
```c
Node* findKthFromEnd(Node* head, int K) {
if (head == NULL) return NULL;
Node* slow = head;
Node* fast = head;
for (int i = 0; i < K; i++) {
fast = fast->next;
}
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
```
4. **输出倒数第K个节点**:
在`findKthFromEnd`函数返回后,打印出节点数据:
```c
void printNode(Node* node) {
printf("倒数第 %d 个节点的数据: %d\n", K, node->data);
}
int main() {
Node* head = NULL; // 初始化链表头部
inputList(&head, K); // 输入链表
Node* kthNode = findKthFromEnd(head, K);
if (kthNode != NULL) {
printNode(kthNode);
}
return 0;
}
```
完整C语言程序查找倒数第k个快慢指针
下面是一个完整的C语言程序,可以实现查找链表中倒数第k个节点的功能。
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* findKthToTail(struct ListNode* head, int k) {
if (head == NULL || k <= 0) {
return NULL;
}
struct ListNode *fast = head;
struct ListNode *slow = head;
for (int i = 0; i < k; i++) {
if (fast) {
fast = fast->next;
} else {
return NULL;
}
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
int main() {
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 1;
head->next = NULL;
struct ListNode *p = head;
for (int i = 2; i <= 10; i++) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = i;
node->next = NULL;
p->next = node;
p = node;
}
struct ListNode *res = findKthToTail(head, 3);
if (res) {
printf("倒数第3个节点的值为:%d\n", res->val);
} else {
printf("链表中没有倒数第3个节点\n");
}
return 0;
}
```
在这个程序中,我们首先定义了一个链表,然后调用了findKthToTail函数来查找倒数第k个节点。最后,将倒数第k个节点的值输出到控制台上。
需要注意的是,为了方便起见,这个程序中只是手动创建了一个链表,实际应用中,链表的创建和初始化可能会有很多不同的方式。