简述C++反转链表 ?
参考答案:
在C++中,反转链表通常涉及遍历链表,逐个改变节点的next
指针方向,使其指向前一个节点。以下是一个简单的C++示例,展示了如何反转一个单链表:
首先,定义链表节点结构:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
然后,实现反转链表的函数:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* nextTemp = curr->next; // 保存下一个节点
curr->next = prev; // 反转当前节点的指针
prev = curr; // prev移动到当前节点
curr = nextTemp; // curr移动到下一个节点
}
return prev; // prev现在指向反转后的链表头部
}
这个函数通过三个指针prev
(前一个节点)、curr
(当前节点)和nextTemp
(下一个节点)来遍历和反转链表。在每次循环中,它先保存当前节点的下一个节点到nextTemp
,然后改变当前节点的next
指针指向前一个节点prev
,接着将prev
和curr
分别移动到当前节点和下一个节点。当curr
到达链表尾部时,prev
就是反转后链表的头部,函数返回prev
。
注意:在实际使用中,你可能需要处理空链表或只有一个节点的情况。在上面的代码中,如果head
为空,函数将返回NULL
,这是正确的行为。