反转链表(Reverse Linked List)是链表中最经典，最基础，最常考的算法题之一.. 反转链表通常有2种实现方法 => 迭代和递归
迭代法 => 推荐
递归法 => 简洁但不一定高效
题目描述
给定一个单链表头指针 head, 将其原地反转，并返回新的头指针
Example: 输入 a->b->c->d->e->NULL
输出 e->d->c->b->a->NULL
解决方案一 迭代法
C++ 代码实现如下
#include <iostream> using namespace std; //链表节点结构 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x),next(null) {} }
ListNode* ReserveListNode(ListNode* head)
{
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr)
{
ListNode* next = cur->next; // 保存下一个节点
cur->next = prev; // 反转指针
prev = cur; // prev 前移
cur = next; // cur 前移
}
return prev; // 最终 prev 是新头
}
解决方案一 递归法
ListNode* reverseListRecursive(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = reverseListRecursive(head->next); head->next->next = head; head->next = nullptr; return newHead; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。