编写一个算法（函数），把一个带头结点的单链表的倒置。

以下是一个基于迭代的算法实现：

def reverse_linked_list(head):
    """
    将带头结点的单链表 head 倒置，并返回新的头结点
    """
    if not head or not head.next:
        return head
    
    # 定义三个指针，分别指向前驱节点、当前节点和后继节点
    pre, cur, nxt = None, head.next, None
    
    while cur:
        nxt = cur.next  # 先保存当前节点的下一个节点
        cur.next = pre  # 将当前节点的 next 指针指向前驱节点
        pre = cur       # 更新前驱节点
        cur = nxt       # 更新当前节点
    head.next = pre     # 更新头结点的 next 指针
    return head

我们首先判断链表是否为空或只有一个节点，如果是的话直接返回头结点。

接着定义三个指针，分别指向前驱节点、当前节点和后继节点。我们从头结点的下一个节点开始，一直迭代到链表末尾。在每次迭代中，我们先保存当前节点的下一个节点，然后将当前节点的 next 指针指向前驱节点，再更新前驱节点、当前节点和后继节点。最后我们更新头结点的 next 指针为倒置后的链表的头节点，并返回头结点。

以上是一个基于迭代的算法实现，也可以使用递归实现。

相关问题

编写一个c语言可执行算法（函数），把一个带头结点的单链表的倒置。

以下是一个基于迭代的 C 语言实现，假设链表的每个节点都是一个结构体类型 `Node`，其中 `next` 指针指向下一个节点：

Node* reverseLinkedList(Node* head) {
    if (!head || !head->next) {
        return head;
    }
    
    Node* pre = NULL;
    Node* cur = head->next;
    Node* nxt = NULL;
    
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    head->next = pre;
    return head;
}

我们首先判断链表是否为空或只有一个节点，如果是的话直接返回头结点。

接着定义三个指针，分别指向前驱节点、当前节点和后继节点。我们从头结点的下一个节点开始，一直迭代到链表末尾。在每次迭代中，我们先保存当前节点的下一个节点，然后将当前节点的 next 指针指向前驱节点，再更新前驱节点、当前节点和后继节点。最后我们更新头结点的 next 指针为倒置后的链表的头节点，并返回头结点。

以上是一个基于迭代的 C 语言实现，也可以使用递归实现。

采用不带头结点的单链表存储， 请设计算法函数linklist reverse1(linklist head) ，将不带头结点的单链表head就地倒置。C语言

在C语言中，不带头节点的单链表反转通常通过迭代或者递归的方式实现。这里提供一个迭代的方法，使用三个指针`prev`, `current` 和 `next`：

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

void linklist_reverse1(Node** head) {
    if (*head == NULL || (*head)->next == NULL) { // 如果链表为空或只有一个元素
        return;
    }
    
    Node* prev = NULL; // 初始化前驱指针
    Node* current = *head; // 初始化当前指针

    while (current != NULL) { // 遍历整个链表
        Node* nextTemp = current->next; // 保存下一个节点
        current->next = prev; // 将当前节点的next指向前一个节点
        prev = current; // 更新前驱指针
        current = nextTemp; // 移动到下一个节点
    }
    
    *head = prev; // 更新头节点为新的头节点（原尾部）
}

这个函数接受链表头节点的地址作为参数，通过不断改变节点的`next`指针，使得整个链表反转。