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

来源：5-7 更多和链表相关的问题

next_n

2019-02-25

老师您好，我在刷题时遇到了“翻转链表”这个问题，题目如下：
输入一个链表，反转链表后，输出新链表的表头。
比如 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老师能否帮忙看看错在哪里？

写回答

3回答

liuyubobobo

2019-02-26

已采纳

你的算法思路没有问题。我在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;
    }
}

继续加油！：）

liuyubobobo

从人从韦

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

2019-05-12

共3条回复