关于单链表反转问题(使用递归实现)

Question

老师,你好.目前,我只想得出来有关它的递归终止条件

    public Node reverseList(Node head) {

    // 如果链表为空或者链表中只有一个元素

    if (head == null || head.next == null) {

                return head;

        }else {    //剩下的就不会了..........

                    return newHead;

        }

Answer 1

liuyubobobo 2018-07-11 00:47:33

在写递归逻辑的时候，一个非常重要的原则就是：使用你涉及的递归函数的宏观语意！在回忆一下我在这个课程中介绍的：递归的过程和子函数调用没有任何区别！只不过我们调用的这个子函数是自己这个函数而已。自己这个函数在做什么事情，我们的子函数调用也在做什么事情。只不过传的参数不同！

再回顾一下我们在第五章写的从链表中删除元素的递归算法：

public ListNode removeElements(ListNode head, int val) {    
    if(head == null)  // 递归终止条件   
        return head;    
        
    // 递归调用
    head.next = removeElements(head.next, val);
    // 此时，我么已经删除了head.next这个链表中所有值为val的元素
    // 因为removeElement做的就是这件事情！
    
    // 我们最后处理当前唯一没有处理的head节点的元素
    return head.val == val ? head.next : head;    
}

 请好好体会一下我在课程中所讲的递归的宏观语意。

现在我们看reverseList。同理，reverseList做的事情就是将传入的链表进行反转，返回新的头结点。所以我们调用reverseList(head.next)，就会将head.next这个链表进行反转，返回新的头结点。我们剩下要处理的，就剩下head节点了：）

整体，我们有以下代码：

public ListNode reverseList(ListNode head) {    
    if (head == null || head.next == null)  // 递归终止条件         
        return head;        
        
    // 将head.next进行反转，反转后的链表的头结点返回给newHead    
    ListNode newHead = reverseList(head.next);    
    // 这里要注意：在链表进行反转以后，head.next仍然指着原先的head.next    
    // 因为我们在reverseList(head.next)的过程中，没有动head!    
    // 只不过此时，原先的head.next，同时是对head.next反转的尾节点    
    // 也就是，现在的head.next，有两个节点的next指着它    
    //    
    // 比如：1->2->3->4->5->NULL    
    // 如果head是2所在的节点的话，我们的这句递归调用，是反转以3为头节点的链表    
    // 运行后的结果应该为：1->2->3<-4<-5，并且返回了5    
    // 对以3为头结点的链表进行反转，结果为5->4->3->NULL，新的链表的头结点为5    
    // 但是由于我们的递归过程和2没有关系，2依然指着3！（2是head，3是head.next）    
    // 我们下面的任务，就是处理这个2(head)   
         
    head.next.next = head; // 3(head.next)相应的next应该指向2(head)    
    head.next = null;      // 2(head)的next赋值为空。    
    
    return newHead;  // 返回newHead}

请再仔细体会一下这个过程。书写递归函数：

1）明确递归函数的宏观语意！说白了就是这个递归函数到底在做什么事情。

2）递归调用的过程，使用这个递归函数，解决一个更小的问题

3）用解决的这个更小的问题的结果，组建当前问题的解（解决了删除head.next中所有的val，如何删除head中所有的val？解决了反转head.next，如何反转head？）

最后，递归算法的编写和设计，确实不容易掌握，需要大量的练习。注意：练习不代表拿100个问题，对每个问题都生想硬看。发现自己没头绪，要马上利用互联网的资源，看别人的解答，别人的分析，体会其中的思路，尽量消化融入到自己的思考路径中。这才是一个学习的过程，进步的过程。一定要善于利用互联网上丰富的资源，为自己所用：）

加油！：）