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 思路

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

实现链表反转步骤如下：

  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 <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->1

5.2 Golang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
		cur := 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;
}
参考文献