LC:反转链表I

题目

给你单链表的头节点 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步骤). 遍历链表的所有节点。

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

[:fist_raised:时间复杂度为 O(n)， 空间复杂度为 O(n)]{.label .success}

代码实现

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 指针，向后移动。

[:fist_raised:时间复杂度是 O(n);空间复杂度是 O(3);]{.label .success}

代码实现

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;
    }
}

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

思路解析

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

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

代码实现

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/

最后

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