设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。

可以使用递归的方式实现单链表的逆序排列。具体实现如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

这个算法的时间复杂度是 O(n)，空间复杂度是 O(n)，其中 n 是单链表的长度。

相关问题

设计一个c语言算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。

以下是一个C语言算法，可以将单链表中的结点以逆序排列：

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

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

void reverseList(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    *head = prev;
}

void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
}

int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    printf("Original List: ");
    printList(head);

    reverseList(&head);

    printf("\nReversed List: ");
    printList(head);

    return 0;
}

这个算法会将单链表中的结点以逆序排列，并且逆序的单链表中的结点均为原表中的结点。

对于不带头结点的单链表 L,设计一个递归算法逆序输出所有结点值。

可以使用递归来实现单链表的逆序输出，具体步骤如下：

1. 首先判断单链表是否为空，若为空则直接返回。
2. 递归输出单链表中除了第一个结点之外的所有结点。
3. 输出第一个结点的值。

以下是递归算法的代码实现：

void reversePrint(Node *head) {
    if (head == NULL) {
        return;
    }
    reversePrint(head->next);
    cout << head->data << " ";
}

其中，`Node` 表示单链表的结点，`head` 表示单链表的头结点。递归函数 `reversePrint` 的功能是逆序输出单链表中所有结点的值。首先判断单链表是否为空，若为空则直接返回。否则，递归输出单链表中除了第一个结点之外的所有结点，并输出第一个结点的值。

需要注意的是，在递归过程中，每次输出结点值的操作都在递归回溯时进行，因此输出的顺序是逆序的。