单链表的反转是一个 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。
下集预报，单链表反转的“二哥”：
- 两两替换链表中的节点