反转链表

题目

反转一个单链表。

示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶：

你可以迭代或递归地反转鍊表。你能否用两种方法解决这道题？

迭代法

从头开始，逐一反转节点。链表的反转本质上是节点之间的链接反转。每个链接关联两个节点，所以每个链接的反转都需要两个节点参与。

假设要反转previous和current之间的链接，

将current指向previous
因为要迭代处理所有链接，所以需要一个变量next去持有current下一个节点

举个例子，反转链表1->2->3->4->5。

首先，previous指向第一个节点，current指向第二个节点，next指向第三个节点。

然后，将current指向previous。

再然后，previous, current, next的指向一起向后移一位。

重复相同的操作，将current指向previous。

把previous, current, next的指向一起向后移一位。

将current指向previous。

把previous, current, next的指向一起向后移一位。

将current指向previous。

代码

package io.github.rscai.leetcode.bytedance.linktree; public class Solution1038A { public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode previous = head; ListNode current = previous.next; previous.next = null; while (current != null) { ListNode next = current.next; current.next = previous; previous = current; current = next; } return previous; } }

复杂度分析

时间复杂度

本演算法遍历了一次链表，时间复杂度为：

$C_{time} = \mathcal{O}(n)$

空间复杂度

使用了三个变量pevious, current, next。空间复杂度：

$C_{space} = \mathcal{O}(1)$

递归法

递归法的一般行式就是把一个问题拆分为一个「小问题」和「其余问题」，然后分别解决一个「小问题」和「其余问题」，最后将结果归併起来。而解决「其余问题」的方法依旧是「拆分为一个小问题和其余问题」，直至「其余问题」与「小问题」一样小。

反转链表问题可以拆分为：

第一个节点
其余链表

先把「其余链表」反转，再把第一个节点接到反转后的「其余链表」的末尾即可。而「其余链表」可以继续拆分，直至仅包含一个元素为止。

举个例子，反转链表1->2->3->4->5。

将其拆分为第一个元素和其余链表。

反转其余链表。将「其余链表」拆分为第一个元素和其余链表。

其余链表仅包含一个元素。复杂程度等同于一个「小问题」。可直接解决（其实就是什么都不做，仅包含一个元素的链就是自身的反向链表）。

然后，归併解。将第一个元素接到已反转的其余链表末尾。

归併解，将第一个元素接到已反转的其余链表末尾。

代码

package io.github.rscai.leetcode.bytedance.linktree; public class Solution1038B { public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode[] reversedHeadAndTail = reverseListRecursive(head); return reversedHeadAndTail[0]; } private ListNode[] reverseListRecursive(ListNode head) { if (head.next == null) { return new ListNode[]{head, head}; } ListNode first = head; ListNode[] remainReversedHeadAndTail = reverseListRecursive(head.next); ListNode reversedHead = remainReversedHeadAndTail[0]; ListNode remainReversedTail = remainReversedHeadAndTail[1]; first.next = null; remainReversedTail.next = first; return new ListNode[]{reversedHead, first}; } }