单链表的反转是一个easy级别的题目，这个题目在力扣上的提交次数达到47万次，而且在面试中也频频呈现，堪称是大受欢迎，它的兄弟们也跟着景色了。这道题自身是比较简单的，而它的“难兄难弟”就不是那么简略了。明天这篇文章先从简略开始，剖析单链表的反转。

题目形容如下。

反转一个单链表。

示例:

输出: 1->2->3->4->5->NULL
输入: 5->4->3->2->1->NULL

办法一：双指针迭代
迭代法在于，在遍历链表的过程中一一扭转链表节点的指向，重点在于在扭转节点指向的同时，不使链表产生断链。咱们能够应用两个变量pre和cur来示意以后拜访到的节点和前一个节点，要使cur.next = pre，为了能使链表持续向前迭代，咱们还须要提前记录以后节点的下一个节点，并把下个节点赋值给cur变量。
动画演示如下。

class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode pre = null, cur = head;        while (cur != null) {            ListNode node = cur.next;            cur.next = pre;            pre = cur;            cur = node;        }        return pre;    }}

复杂度剖析

  • 工夫复杂度：O(n)。
  • 空间复杂度：O(1)。

办法二：递归
递归是个神奇的存在，那么简略，又那么简单，有时感觉它很近，实际上它却那么远，有时感觉重新认识了它，可它还是那个它，从未扭转过。每一次应用递归，都会对它了解更深一点。

递归法解决链表反转在于假如曾经反转好链表的其余节点，以后节点怎么解决。假如链表为

$$N_1 \rightarrow N2 \rightarrow ... \rightarrow N_k \rightarrow N_{k+1} \rightarrow ... \rightarrow N_n$$

如果$N_{k+1}$到$N_n$局部曾经反转实现，那么链表的构造是这个样子的：

$$N_1 \rightarrow N2 \rightarrow ... \rightarrow N_k \rightarrow N_{k+1} \leftarrow ... \leftarrow N_n$$

以后节点在$N_{k}$的地位，为了使$N_{k+1}$和$N_k$的指向进行扭转，咱们要做如下操作：

$$N_k.next.next = N_k$$

代码如下：

class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode node = reverseList(head.next);        head.next.next = head;        head.next = null;        return node;    }}

链表反转应用递归，是让人感觉很惊艳的解法，但也不太好了解，上面借助动画慢放递归调用的过程。

复杂度剖析

  • 工夫复杂度：O(n)。
  • 空间复杂度：O(n)，应用了递归，递归的栈深度为n。

下集预报，单链表反转的“二哥”：

  • 两两替换链表中的节点