链表递归

题目链接：

https://leetcode.cn/problems/reverse-linked-list/

方案一：

解题思路：

  • 先借助一个额外的 List 来将各节点存储下来
  • 反向遍历这个 List，然后构造最终结果

  • 优化思路：去掉额外的 List，重构代码

    解题代码：

    1. class Solution {
    2.   public ListNode reverseList(ListNode head) {
    3.       if (head == null) {
    4.           return null;
    5.       }
    6.       ListNode previous= null;
    7.       ListNode current = head;
    8.       while (current != null) {
    9.           previous = new ListNode(current.val, previous);
    10.           current = current.next;
    11.       }
    12.       return previous;
    13.   }
    14. }

    运行结果：

    image.png

    复杂度分析：

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

    引发的思考：

    上诉的代码并不是一开始想到的，而是重构出来的；
    最初的思路是先借助一个额外的 List 来将各节点存储下来，然后遍历 List 的过程中重新构造最终结果
    通过上一步先实现功能，然后寻找共同点，将额外的 List 去掉后，将第 2 个遍历代码合并到 While 循环中即可