【LeetCode】反转链表 Java 题解

2021 年 11 月 16 日
本文字数：979 字
阅读完需：约 3 分钟

题目描述

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

示例 1：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]输出：[2,1]
示例 3：
输入：head = []输出：[]
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-linked-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是链表处理题目。那什么是链表呢？链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而线性表和顺序表相应的时间复杂度分别是 O(logn)和 O(1)。
了解了链表的基本定义，结合题目给出的单链表，我们可以将这个题目分步解决，首先是遍历链表的每一个节点，采用 while (head != null) {} 循环遍历，链表的最后一个节点是 null, 我们找到了 null 节点，就遍历完成了。
第二步，我们分析反转的过程，首先暂存 head.next 节点，然后将 head.next 指向上一个 last 节点，在更新当前的 last 节点，逐个反转。具体实现代码如下：

通过代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode reverseList(ListNode head) {        ListNode last = null;         while (head != null) {            ListNode nextNode = head.next;            head.next = last;            last = head;            head = nextNode;        }        ListNode ans = last;        return ans;    }}