设计一个算法,将带头结点的单链表逆置。
时间: 2023-05-17 13:06:39 浏览: 128
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
可以使用三个指针来实现单链表的逆置,具体步骤如下:
1. 定义三个指针:pre、cur、next,分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。
2. 将 cur 指向头结点的下一个节点,pre 指向头结点,next 指向 cur 的下一个节点。
3. 依次遍历链表,将 cur 的 next 指向 pre,然后将 pre、cur、next 分别向后移动一个节点。
4. 当 next 为空时,说明已经遍历完整个链表,此时将头结点的 next 指向 pre,即完成了链表的逆置。
下面是具体的代码实现:
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* pre = head;
ListNode* cur = head->next;
ListNode* next = cur->next;
while (next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = cur;
}
注意,这里假设链表带有头结点,如果不带头结点,需要对代码进行相应的修改。
阅读全文