将一个不含有头结点的链表倒置
时间: 2023-05-27 17:07:52 浏览: 60
假设原链表为 L,倒置后的链表为 L'。
1. 定义三个指针 pre、cur 和 next,初始时 pre 和 cur 指向 NULL,next 指向 L 的第一个结点。
2. 遍历原链表 L,将 L 中的每个结点插入到 L' 的头部,即将 next 插入到 L' 的头部。
a. 首先将 next 的后继结点保存在 next 中。
b. 然后将 next 插入到 L' 的头部。
- 将 next 的后继结点指向 L' 的第一个结点。
- 将 L' 的头指针指向 next。
c. 将 cur 指向 next,将 next 指向 pre。
d. 将 pre 指向 cur,将 cur 指向 next。
3. 遍历完原链表 L 后,L' 中的结点顺序就是倒置后的顺序。
4. 返回 L' 的头指针。
下面是具体的代码实现:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode *pre = NULL, *cur = NULL, *next = head;
while (next != NULL) {
cur = next;
next = next->next;
cur->next = pre;
pre = cur;
}
return cur;
}
```