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

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

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. 初始化两个指针，分别命名为 `prev` 和 `current`，初始都设置为 `NULL`。`prev` 用于存储当前节点的前一个节点，而 `current` 则指向当前正在处理的节点，即链表头部的 `L`。

2. 当 `current` 不为 `NULL` 时，执行以下操作：
a. 将 `current` 的下一个节点赋值给临时变量 `next`，保存当前节点的后继节点。
b. 将 `current` 的指向前驱设为 `prev`，使其反转链接。
c. 更新 `prev` 指向 `next`，即将 `prev` 移动到下一个位置。
d. 将 `current` 赋值为 `next`，继续处理下一位节点。

3. 遍历结束后，`current` 就会变成 `NULL`，此时 `prev` 就是指向原链表尾部的节点，它之前的所有节点已经被逆序连接。所以，只需将 `prev` 指向的节点设置为新的链表头 `L`，就可以完成整个链表的逆序。

以下是伪代码形式的算法：

L = 单链表头
prev = NULL
current = L

while current != NULL:
    next = current.next
    current.next = prev  # 反转当前节点的指向
    prev = current       # 更新前驱节点
    current = next       # 继续遍历

if prev != NULL:  # 如果不是空链表
    L = prev  # 新的头节点是之前的尾节点