[已解决]输出单链表倒数第K个结点值

yangzhixiaohuli

【问题描述】

输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。

【输入形式】

输入第一位为K值，其后接一串以空格分隔的整型值。
【输出形式】

输出为倒数第K个结点的值，若无，则输出Not Found

【样例输入】

3 13 45 54 32 1 4 98 2
【样例输出】

4
【样例说明】

K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
【评分标准】

本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。

这题用C怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-25 20:09:01

要在C语言中实现输出单链表倒数第K个结点值，以下是完整的代码示例和注释。该示例通过构建链表，然后利用双指针方法找到倒数第K个结点。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建链表结点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 构建链表
Node* buildList(int* array, int size) {
    if (size == 0) return NULL;
    Node* head = createNode(array[0]);
    Node* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(array[i]);
        current = current->next;
    }
    return head;
}

// 找到倒数第K个结点
int findKthToLast(Node* head, int k) {
    if (!head || k <= 0) return -1;
    Node *fast = head, *slow = head;

    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return -1; // 链表长度不足k
        fast = fast->next;
    }

    // 快慢指针一起走
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow->data;
}

int main() {
    int k;
    printf("请输入K值：");
    scanf("%d", &k);

    char buffer[1024];
    printf("请输入链表值：");
    scanf(" %[^\n]s", buffer);

    int array[100], size = 0;

    char* token = strtok(buffer, " ");
    while (token != NULL) {
        array[size++] = atoi(token);
        token = strtok(NULL, " ");
    }

    Node* head = buildList(array, size);
    int result = findKthToLast(head, k);
    if (result == -1) {
        printf("Not Found\n");
    } else {
        printf("%d\n", result);
    }

    // 释放链表内存
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

### 代码解析
1. **链表节点的结构**：定义了一个结构体`Node`，包含整型数据`data`和指向下一个节点的指针`next`。
2. **创建节点函数**：`createNode`用于创建一个新的节点。
3. **构建链表函数**：`buildList`通过传入的数组和数组大小来构建链表。
4. **寻找倒数第K个节点函数**：
   - `findKthToLast`通过使用两个指针`fast`和`slow`，利用双指针的方式找到倒数第K个结点。
   - 先让`fast`指针前进K步，然后`fast`与`slow`指针同时前进，直到`fast`到达链表末尾，此时`slow`指针指向的就是倒数第K个节点。
5. **主函数**负责读取输入、构建链表、调用查找函数并输出结果，同时释放链表内存。

### 执行步骤
1. 用户输入K值和链表节点值。
2. 程序将输入的节点值存储在数组中并构造链表。
3. 调用`findKthToLast`函数查找倒数第K个节点。
4. 输出结果，若未找到则输出`Not Found`。
5. 释放动态分配的链表内存。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要在C语言中实现输出单链表倒数第K个结点值，以下是完整的代码示例和注释。该示例通过构建链表，然后利用双指针方法找到倒数第K个结点。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建链表结点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 构建链表
Node* buildList(int* array, int size) {
    if (size == 0) return NULL;
    Node* head = createNode(array[0]);
    Node* current = head;
    for (int i = 1; i < size; i++) {
        current->next = createNode(array[i]);
        current = current->next;
    }
    return head;
}

// 找到倒数第K个结点
int findKthToLast(Node* head, int k) {
    if (!head || k <= 0) return -1;
    Node *fast = head, *slow = head;

    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return -1; // 链表长度不足k
        fast = fast->next;
    }

    // 快慢指针一起走
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow->data;
}

int main() {
    int k;
    printf("请输入K值：");
    scanf("%d", &k);

    char buffer[1024];
    printf("请输入链表值：");
    scanf(" %[^\n]s", buffer);

    int array[100], size = 0;

    char* token = strtok(buffer, " ");
    while (token != NULL) {
        array[size++] = atoi(token);
        token = strtok(NULL, " ");
    }

    Node* head = buildList(array, size);
    int result = findKthToLast(head, k);
    if (result == -1) {
        printf("Not Found\n");
    } else {
        printf("%d\n", result);
    }

    // 释放链表内存
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

### 代码解析
1. **链表节点的结构**：定义了一个结构体`Node`，包含整型数据`data`和指向下一个节点的指针`next`。
2. **创建节点函数**：`createNode`用于创建一个新的节点。
3. **构建链表函数**：`buildList`通过传入的数组和数组大小来构建链表。
4. **寻找倒数第K个节点函数**：
   - `findKthToLast`通过使用两个指针`fast`和`slow`，利用双指针的方式找到倒数第K个结点。
   - 先让`fast`指针前进K步，然后`fast`与`slow`指针同时前进，直到`fast`到达链表末尾，此时`slow`指针指向的就是倒数第K个节点。
5. **主函数**负责读取输入、构建链表、调用查找函数并输出结果，同时释放链表内存。

### 执行步骤
1. 用户输入K值和链表节点值。
2. 程序将输入的节点值存储在数组中并构造链表。
3. 调用`findKthToLast`函数查找倒数第K个节点。
4. 输出结果，若未找到则输出`Not Found`。
5. 释放动态分配的链表内存。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

jackz007

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
        typedef struct chain {
                int data                                                            ;
                struct chain * next                                                 ;  
        } CHAIN , * PCHAIN                                                          ;
        PCHAIN head , p , q                                                         ;
        int d , i , k , n , r                                                       ;
        printf("Enter the data : ")                                                 ;
        for(r = 1 , n = 0 ;; n ++) {
                scanf("%d" , & d)                                                   ;
                if(! n) {
                        k = d                                                       ;
                } else {
                        if (p = (PCHAIN) malloc(sizeof(CHAIN))) {
                                p -> data = d                                       ;
                                p -> next = NULL                                    ;
                                if(n == 1) head = p                                 ;
                                else q -> next = p                                  ;
                                q = p                                               ;
                         } else {
                                fprintf(stderr , "malloc() failure !\n")            ;
                                r = 0                                               ;
                                break                                               ;
                        }
                }
                if(getchar() =='\n') break                                          ;
        }
        if(r) {
                for(i = 0 , p = head ; p && i < n - k ; i ++) p = p -> next         ;
                if(p) printf("%d\n" , p -> data)                                    ;
                else printf("not found !\n")                                        ;
                for(p = head ; p ; p = q ) {
                        q = p -> next                                               ;
                        free(p)                                                     ;
                }
        }
}