数据结构实现单链表反转

单链表反转可以通过遍历链表，将每个节点的指针指向其前驱节点来实现。具体实现步骤如下：

1. 定义三个指针：pre、cur、next，分别表示当前节点的前驱节点、当前节点和后继节点。
2. 将 cur 指向链表的头节点。
3. 遍历链表，每次循环执行以下操作：
- 将 next 指向 cur 的后继节点。
- 将 cur 的指针指向 pre。
- 将 pre 指向 cur。
- 将 cur 指向 next。
4. 遍历结束后，将链表的头节点指向 pre。

下面是单链表反转的 Python 代码实现：

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

def reverseList(head: ListNode) -> ListNode:
    pre, cur = None, head
    while cur:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    return pre

相关问题

数据结构C语言实现单链表逆置

在C语言中，单链表的逆置是一个常见的操作。逆置单链表意味着将链表的指针方向反转，使得最后一个节点变成第一个节点，依此类推。以下是一个简单的实现方法：

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 逆置单链表
Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;

    while (current != NULL) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 反转当前节点的指针
        prev = current;       // 移动prev指针
        current = next;       // 移动current指针
    }

    return prev; // 返回新的头节点
}

// 打印单链表
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 主函数
int main() {
    // 创建链表 1->2->3->4->NULL
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("原始链表: ");
    printList(head);

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

    printf("逆置后链表: ");
    printList(head);

    return 0;
}

在这个实现中，`reverseList`函数通过三个指针`prev`、`current`和`next`来逆置链表。`current`指针遍历链表，`next`指针保存当前节点的下一个节点，`current->next`指针反转指向`prev`，然后`prev`和`current`指针分别向前移动。