首页 LeetCode 系列

# 题目

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

示例一

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例二

输入：head = [1,2]
输出：[2,1]

示例三

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

力扣（LeetCode）206.反转链表

https://leetcode-cn.com/

# 分析

这是一道非常简单的题目。也是很容易出现达克效应的一道题目。 为什么呢？应为这道题太简单了啊。 思路 太简单了啊。 但是真正去写的话，可不见得真有那么简单。

简单的题目，我们还是 以图的形式来展示。

# 思路一：迭代链表，创建新节点，重组成新链表

# 思路解析

一图胜千言

核心思路如标题。 首先将遍历的原链表中的节点值复制到新建的节点中 (a 步骤), 节点 next 指针指向是上一个节点，没有则为 null (b 步骤). 遍历链表的所有节点。

这样其实会生成一个新的链表。也就说会同时存在两条链表。

✊时间复杂度为 O (n)， 空间复杂度为 O (n)

# 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {

    public ListNode reverseList(ListNode head) {

        // 非空判断
        if (null == head || null == head.next) {
            return head;
        }

        // 遍历旧链表,新建节点，并且拼接成新链表。
        ListNode pre = null;
        while (null != head) {
            ListNode curr = new ListNode(head.val);
            curr.next = pre;
            pre = curr;
            head = head.next;
        }
        return pre;
    }
}

# 思路二：迭代变更链表的指针指向

# 思路解析

这种思路也是比较简单的，但是一定要想好喽之后，再看开始编码，要不然很容易思绪错乱。

图解:

一图胜千言

这种解法需要两个指针， pre 代表其前一个节点， cur 代表后一个节点。进行遍历，从而实现 指针指向的变更。 当然，还需要一个临时节点去帮忙 pre 和 cur 指针，向后移动。

✊时间复杂度是 O (n); 空间复杂度是 O (3);

# 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution2 {

    public ListNode reverseList(ListNode head) {
        // 非空判断
        if (null == head || null == head.next) {
            return head;
        }
        ListNode pre = head, cur = head.next;
        // !!注意:断开头节点的next指针，避免产生环型链表。
        pre.next = null;
        while (null != cur) {
            ListNode tempNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tempNode;
        }
        return pre;
    }
}

# 思路三：递归方式， 变更指针

# 思路解析

这思路三，其实是思路二的不同写法。 这种实现方法首先就需要将 链表 “递” 到底，然后在归的时候，把 节点链接到一起。如下图

一图胜千言

这样说起来，递归这种方式来解决反转类的问题好像会有一种与生俱来的优势。 首先递进去，然后归出来 。

# 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution3 {

    public ListNode reverseList(ListNode head) {
        // 非空判断
        if (null == head || null == head.next) {
            return head;
        }

        // 递归入口
        return reverse(head, null);
    }

    public ListNode reverse(ListNode currNode, ListNode preNode) {
        ListNode headNode = null;
        if (null == currNode) {
            headNode = preNode;
        } else {
            headNode = reverse(currNode.next, currNode);
            currNode.next = preNode;
        }
        return headNode;
    }
}

# 思考

这一道题考的是简单的逻辑问题，实属简单至极的题目。要注意 陷入 “达克效应”。

勿以题小而不做。

使用头递归来做反转类似的题目，好像是一种天然支持的特性。但是在实际的开发过程中，不建议过多的使用递归的方式，一方面不具备可读性。另一方面，递归方式对性能不太优化，还有重要的是要考虑栈溢出的风险。

# 相关题目

力扣（LeetCode）189.反转数组

https://leetcode-cn.com/

力扣（LeetCode）92.反转链表II

https://leetcode-cn.com/

力扣（LeetCode）7.整数反转

https://leetcode-cn.com/

力扣（LeetCode）344.反转字符串

https://leetcode-cn.com/

# 最后

期望与你一起遇见更好的自己

期望与你一起遇见更好的自己