1. 全栈程序员必看首页

反转链表（leetcode 206）

全栈程序员-站长 • • 未分类 • 阅读 2

反转链表（leetcode 206）1 题目单向链表反转是一道经典的求职面试笔试或机试题 给定如下如下链表的节点定义 structLinkNo intvalue LinkNode next 比如有一个链表是这样的 1 gt 2 gt 3 gt 4 gt 5 反转后成为 5 gt 4 gt 3 gt 2 gt 1 请实现函数 LinkNode Reverse LinkNode h

文章目录

1.问题描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

2.难度等级

easy。

3.热门指数

★★★★★

出题公司：腾讯、阿里、百度、字节、虾皮等，极其热门，务必掌握。

4.解题思路

4.1 思路

反转链表是一道经典的面试题。

实现链表反转步骤如下：

  1. 使用一个全局变量保留每个结点的前驱结点，记为 pre。
  2. 从第一个节点开始遍历，临时保存当前结点的 next 结点，变更当前结点的 next 指针指向前驱结点 pre。
  3. 当前结点作为前驱结点赋给 pre，当前结点的 next 结点赋值给当前结点，继续迭代，直到为 NULL。

4.2 复杂度分析

  • 时间复杂度

O(n)，n 为链表长度。遍历一遍链表即可完成反转。

  • 空间复杂度

O(1)，借助的中间变量占用空间为常数级。

5.实现示例

5.1 C++

struct LinkNode { 
    int value; LinkNode* next; }; // Reverse 实现单向链表反转（迭代方式）。 LinkNode* Reverse(LinkNode* header) { 
    LinkNode* pre = NULL, *cur = header; while(cur != NULL) { 
    auto next = cur-> next; cur->next = pre; pre = cur; cur = next; } return pre; }

验证：

// //@brief: main.cpp // #include  
     using namespace std; // printLink 打印单向链表。 void printLink(LinkNode* header) { 
    while(header != NULL) { 
    cout<< header->value; header = header->next; if (header != NULL) { 
    cout<< "->"; } } } int main(int argc, char* argv[]) { 
    // 创建单向链接。 LinkNode* header = NULL, *cur = NULL; for(int i = 1; i <= 5; ++i) { 
    LinkNode* node = new LinkNode; node->value = i; node->next = NULL; if (header == NULL) { 
    header = node; cur = header; } else { 
    cur->next = node; cur = node; } } printLink(header); // 反转单向链表。 auto newHeader = Reverse(header); printLink(newHeader); }

编译执行输出：

g++ -std=c++11 main.cpp ./a.out 1->2->3->4->5 5->4->3->2->1

5.2 Golang

type LinkNode struct { 
    value int next *LinkNode }; // ReverseList 反转链表。 func ReverseLit(head *LinkNode) *LinkNode { 
    pre, cur := nil, head for cur != nil { 
    next := cur.next cur.next = pre pre = cur cur = next } return pre }

6.其他解法（递归）

6.1 解题思路

从倒数第二个节点开始反转，依次向前，将后一个节点的 next 指向当前节点。注意每次反转后要将当前节点的 next 置空，表示断开当前节点与后一个节点的关联。此种方法可以使用递归来实现。

由于每次递归都需要为实参分配空间，所以相较于非递归实现，较耗费栈空间，且不易理解。

6.2 实现示例

// Reverse 实现单链表反转（递归方式）。 LinkNode* Reverse(LinkNode * head) { 
    // 递归终止条件：找到链表最后一个结点。 if (head == NULL || head->next == NULL) { 
    return head; } LinkNode * newhead = Reverse(head->next); // 先递后归，从后往前遍历每个节点进行反转 head->next->next = head; // 将当前结点的后一个结点的 next 指向当前结点 head->next = NULL; // 断开当前结点指向后一个结点 return newhead; }

参考文献

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199604.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月20日 下午12:38
下一篇 2026年3月20日 下午12:38


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号