设计一个算法，将带头的单链表逆置

设计一个算法来逆置带头的单链表，可以采用迭代或递归的方式。这里我们提供一种迭代的方法，它更直观且空间复杂度较低。

**迭代法（非递归）：**

1. 定义两个指针，`prev` 和 `curr`，初始都指向头节点 `head`。
2. 创建一个临时变量 `nextNode`，用于保存当前节点的下一个节点。
3. 进入循环，当 `curr` 不为空时，执行以下步骤：
- 将 `curr` 的下一个节点赋值给 `nextNode`。
- 更新 `curr` 指向 `prev`。
- 更新 `prev` 指向 `curr`（即原 `curr.next`）。
4. 循环结束后，`prev` 就是指向了新的头节点，因为原来的头节点现在变成了最后一个节点。所以返回 `prev` 作为新链表的头。

下面是伪代码形式：

def reverseList(head):
    prev = None
    curr = head

    while curr is not None:
        nextNode = curr.next
        curr.next = prev
        prev = curr
        curr = nextNode
    
    return prev

相关问题

用c语言设计一个算法，将带头的单链表逆置

在 C 语言中，我们可以使用迭代的方式来设计一个简单算法来逆置带头结点的单链表。这里是一个基本的步骤：

1. 定义两个指针，`prev` 和 `current`，初始时都指向头节点。
2. 当 `current` 指针不为空时，进行循环操作：
- 将 `current` 的下一个节点赋值给 `temp`（临时存储当前节点的下一个节点）
- 更新 `current` 的下一个节点为 `prev`
- 移动 `prev` 和 `current` 向前，即 `prev = current`, `current = temp`
3. 循环结束后，`prev` 就指向了新的头节点。

下面是对应的伪代码和 C 语言代码实现：

// 结构体定义链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 函数定义逆置链表
Node* reverseList(Node* head) {
    Node* prev = NULL; // 初始化prev为NULL
    Node* current = head; // 初始化current为头节点

    while (current != NULL) { // 当current非空时
        Node* temp = current->next; // 保存当前节点的下一个
        current->next = prev; // 更新当前节点的next为prev
        prev = current; // 移动prev
        current = temp; // 移动current
    }
    return prev; // 返回新头节点
}

设计一个算法，将带头的单链表逆置的代码

设计一个算法反转单链表的代码通常涉及创建一个新的头节点和两个指针，一个是原来的头节点，另一个是新的头节点。以下是使用Python语言的一个简单示例：

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

def reverseList(head):
    prev = None  # 新的头节点
    current = head  # 当前节点

    while current is not None:
        next_temp = current.next  # 保存当前节点的下一个节点
        current.next = prev  # 将当前节点指向prev
        prev = current  # 更新prev指向前一个节点
        current = next_temp  # 移动current到下一个节点

    return prev  # 返回新链表的头节点

# 示例
# 假设我们有链表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

reversed_head = reverseList(head)

这个算法的时间复杂度是O(n)，因为需要遍历整个链表一次。空间复杂度是O(1)，因为它只用了几个额外的变量，并未增加数据结构。