利用链表的递归性质求解“链表翻转”问题

Question

老师您好，我在刷题时遇到了“翻转链表”这个问题，题目如下：
输入一个链表，反转链表后，输出新链表的表头。
比如 1->2->3->4->5 要变成 1<-2<-3<-4<-5
当然，这个问题很简单，用普通方法可以简单得到如下解：
（1）非递归思路

public class Solution {
        public ListNode ReverseList(ListNode head) {
            if(head == null) return null;
            if(head.next == null) return head;
            ListNode p = ReverseList(head.next);
            ListNode q = p;
            while (q.next != null){
                q = q.next;
            }
            q.next = head；
            return p;
        }
    }

但是听了你的课以后，我一直尝试用递归的思想去求解这个问题，（但是出现了问题，所以特地来这一章节向您提问）解法如下：
（2）递归思路求解

public class Solution {
    public ListNode ReverseList(ListNode head) {
	    //递归到底的结果
        if(head == null) return null;
        if(head.next ==null) return head;
        //假设ReverseList(head.next)已经将以head.next为头结点的链表翻转；
        //同时返回翻转后链表的头节点reverse_head_next
        //那么接下来的工作就是将head节点加入这个翻转后的链表里。
        ListNode reverse_head_next = ReverseList(head.next);
        //q用来遍历到链表的末尾，"接住"head;
        ListNode q = reverse_head_next;
        while (q.next != null){
            q = q.next;
        }
        q.next = head;
        return reverse_head_next;
        }
    }

当然这个解法是错的，bobo老师能否帮忙看看错在哪里？

Answer 1

liuyubobobo 2019-02-26 01:52:59

你的算法思路没有问题。我在Leetcode上测试了一下你的代码（206号问题），会报超时。

原因在于，你的这个递归算法，是一个O(n^2)复杂度的算法。可以想象一下，每一次递归调用，你都确定了一个节点如何和剩下的节点进行连接。为了确定这个连接方式，你还需要遍历一遍剩下的所有节点。所以整体是O(n^2)的。而相应的非递归算法是O(n)的：）

解决方法很简单。我们不能每次递归调用“遍历到链表的末尾”，看能否能直接获得翻转链表的末尾？当然可以啦！翻转后链表的末尾，就是翻转前链表的头啊！范赚钱链表的头，就是head.next啊！：）

我修改的代码如下：

public class Solution {
    public ListNode reverseList(ListNode head) {
        //递归到底的结果
        if(head == null) return null;
        if(head.next ==null) return head;
        
        //假设ReverseList(head.next)已经将以head.next为头结点的链表翻转；
        //同时返回翻转后链表的头节点reverse_head_next
        //那么接下来的工作就是将head节点加入这个翻转后的链表里。
        ListNode reverse_head_next = reverseList(head.next);
        
        // 上面的代码递归处理完了head.next对应的链表
        // 下面的代码用来维护head
        ListNode reverse_tail = head.next; // 这个变量不声明也可以，声明语义更清晰：）
        reverse_tail.next = head;
        head.next = null;
        
        return reverse_head_next;
    }
}

继续加油！：）

• 提问者 next_n #1

  哈哈，我好蠢！感谢老师！

• 从人从韦 #2

  计算机擅长做重复的事情，所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
  对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。很多时候，我们理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢？
  如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
  因此，编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

• liuyubobobo 回复 从人从韦 #3

  大赞！所谓的递归宏观语义：）感谢分享：）

Answer 2

提问者 next_n 2019-02-25 21:19:54

很尴尬。。非递归思路贴错了（贴成了和下面递归思路一样的），不过就是常规方法，很简单。就不再贴了。麻烦帮忙看看“递归思路”的错误。

Answer 3

提问者 next_n 2019-02-25 21:14:35

//ListNode 定义如下：

public static class ListNode {
   int val;
   ListNode next = null;

   ListNode(int val) {
       this.val = val;
   }
}