反转链表（leetcode 206）
文章目录
1.问题描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1： 给定单向链表 1->2->3->4->5，反转后为 5->4->3->2->1。
示例 2： 给定单向链表 1->2->3，反转后为 3->2->1。
示例 3： 给定空链表 ，返回空链表。
2.难度等级
easy。
3.热门指数
★★★★★
出题公司：腾讯、阿里、百度、字节、虾皮等，极其热门，务必掌握。
4.解题思路
4.1 思路
反转链表是一道经典的面试题。
实现链表反转步骤如下：
- 使用一个全局变量保留每个结点的前驱结点，记为 pre。
- 从第一个节点开始遍历，临时保存当前结点的 next 结点，变更当前结点的 next 指针指向前驱结点 pre。
- 当前结点作为前驱结点赋给 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 <iostream>
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->15.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 置空，表示断开当前节点与后一个节点的关联。此种方法可以使用递归来实现。
时间复杂度 O(n)； 空间复杂度 O(n)。
由于每次递归都需要为实参分配空间，所以相较于非递归实现，较耗费栈空间，且不易理解。
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;
}参考文献
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录