采用递归方式求不带头结点的单链表的长度的C语言代码

int getLength(Node* head) {
    if(head == NULL) { // 空链表
        return 0;
    }
    else {
        return 1 + getLength(head->next); // 递归求解
    }
}

其中，Node为单链表节点的结构体定义。

相关问题

c语言编程实现已知带头结点单链表L，编写函数删除倒数第k个结点，删除成功函数返回1，否则返回0

在 C 语言中，实现删除单链表 L 中倒数第 k 个节点，需要考虑到链表长度不确定的情况，以及当 k 大于链表长度时的情况。这里提供一种常见的递归解决方案：

首先，我们需要定义链表结构体 `ListNode` 和一些辅助函数：

// 定义链表节点结构
typedef struct ListNode {
    int val;        // 节点值
    struct ListNode* next;   // 指向下一个节点的指针
} ListNode;

// 创建一个新的链表节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 删除链表中的倒数第 k 个节点
int removeKthFromEnd(ListNode* head, int k) {
    if (!head || !head->next) {       // 链表为空或只有一个节点
        return (k == 1) ? 0 : -1;    // 如果 k 等于 1，则直接返回 0 或 -1 表示失败
    }

    // 使用两个指针，快慢指针，快指针每次走两步，慢指针每次走一步
    ListNode* slow = head;
    ListNode* fast = head->next;

    // 让快指针走到链表末尾
    for (int i = 1; fast && fast->next; ++i) {
        fast = fast->next->next;
    }
    
    // 如果 k > 链表长度，返回 0，表示删除失败
    if (!fast || k > i + 1) {
        return 0;
    }

    // 从头开始，慢指针每移动一次，快指针就前移 k - 1 次，直到找到倒数第 k 个节点
    while (k--) {
        fast = fast->prev;
    }

    // 删除找到的节点，将前一个节点的 next 指针指向下一个节点
    ListNode* temp = slow->prev;
    if (temp) {
        temp->next = slow->next;
    } else {     // 如果是头节点，头指针直接指向下一个节点
        head = slow->next;
    }
    free(slow);      // 释放被删除节点的内存

    return 1;         // 删除成功，返回 1
}

在这个函数里，我们通过快慢指针定位到倒数第 k 个节点，然后删除它。需要注意的是，如果链表长度小于 k，或者 k 等于链表长度，这个操作无法完成，此时返回 0 表示失败。

对于一个不带头结点的单链表L，设计一个递归算法逆置所有结点。编写完整的程序并进行测试，分析其时间复杂度。用c语言编写

好的，这个问题我可以回答。以下是递归算法的代码：

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

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

Node* reverseList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

int main() {
    // 创建一个不带头结点的单链表
    Node* head = NULL;
    for (int i = 1; i <= 5; i++) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = i;
        node->next = head;
        head = node;
    }

    // 输出原链表
    printf("原链表：");
    Node* p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    // 逆置链表
    head = reverseList(head);

    // 输出逆置后的链表
    printf("逆置后的链表：");
    p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    return 0;
}

时间复杂度分析：递归算法的时间复杂度为 O(n)，其中 n 是链表的长度。因为每个结点只会被遍历一次。