Leetcode 刷题

剑指 Offer 24. 反转链表

  • 难度：简单

题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例1

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

提示

  • 0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

双指针

class Solution {
public:
    
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = head, *cur = NULL;
        while(pre != NULL){
            ListNode* ele = pre->next;
            pre -> next = cur;
            cur = pre;
            pre = ele;
        }
        return cur;
    }
};

思路

  • 链表操作一定要在纸上将过程画出来！
  1. 定义两个指针，pre和cur；一前一后，pre在前，cur在后。
  2. 每次让pre的next指向cur，实现局部反转。
  3. 然后pre和cur同时往前移动一位。
  4. 循环1～3，直到链表末尾。

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};

题解学习leetcode答者@Chuancey，大佬的讲解让我受益匪浅。

解题思路

这个思路对写递归代码来说，还是比较简单适用的，比我看到的这些把递归掰开来揉碎了来讲的要更容易出代码。希望对写递归还比较迷茫的同学们有所帮助，如果我写的对你有帮助，还望大家能多点赞转发。

Rules Number One

基本上，所有的递归问题都可以用递推公式来表示。有了这个递推公式，我们就可以很轻松地将它改为递归代码。

所以，遇到递归不要怕，先想递推公式。

例1: (比较明显的能递推公式的问题)

  • 问题：斐波那契数列的第n项

  • 递推公式：

    f(n)=f(n-1)+f(n-2) 其中，f(0)=0,f(1)=1

  • 终止条件：

    if (n <= 2) return 1;

  • 递归代码：

    int f(int n) {
      if (n <= 2) return 1;
      return f(n-1) + f(n-2);
    }
例2:(不那么明显的有递推公式的问题)

  • 问题：逆序打印一个数组

  • 递推公式：

    假设令F(n)=逆序遍历长度为n的数组
    那么F(n)= 打印数组中下标为n的元素 + F(n-1)

  • 终止条件：

    if (n <0) return ;

  • 递归代码：

    public void Print(int[] nums,int n){
        if(n<0) return;
        System.out.println(nums[n]);
        Print(nums,n-1);
    }

到这里，不知道大家对写递归有没有一些理解了。其实写递归不能总想着去把递归平铺展开，这样脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。只要找到递推公式，我们就能很轻松地写出递归代码。

到这里，我想进一步跟大家说明我这个思路是比较能够容易出代码的，那么就树的遍历问题来和大家讲。递归总是和树分不开，其中，最典型的便是树的遍历问题。刚开始学的时候，不知道大家是怎么理解先／中／后序遍历的递归写法的，这里我提供我的思路供参考，以前序遍历为例：

  • 问题：二叉树的先序遍历

  • 递推公式：

    令F(Root)为问题:遍历以Root为根节点的二叉树，
    令F(Root.left)为问题:遍历以F(Root.left)为根节点的二叉树
    令F(Root.right)为问题:遍历以F(Root.right)为根节点的二叉树
    那么其递推公式为：
    F(Root)=遍历Root节点+F(Root.left)+F(Root.right)

  • 递归代码：

    public void preOrder(TreeNode node){
        if(node==null) return;
        System.out.println(node.val);
        preOrder(node.left);
        preOrder(node.righr);
    }

Rules Number Two

递归是一种关于某个重复动作(完成重复性的功能)的形式化描述。

具体点讲，如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系(也就是说，递归只能考虑当前层和下一层的关系，不能继续往下深入)。我们需要屏蔽掉递归细节，理解为完成了某种功能的形式化描述即可。

  • 问题：单向链表的反转

  • 递推公式：

    令F(node)为问题:反转以node为头节点的单向链表；
    一般，我们需要考虑F(n)和F(n-1)的关系，那么这里，如果n代表以node为头节点的单向链表，那么n-1就代表以node.next为头节点的单向链表.
    所以，我们令F(node.next)为问题：反转以node.next为头节点的单向链表；
    那么，F(node)和F(node.next)之间的关系是？这里我们来简单画个图，假设我们反转3个节点的链表：
    1 -> 2 -> 3
    那么，F(node=1)=F(node=2)+?
    这里假设子问题F(node=2)已经解决，那么我们如何解决F(node=1)：
    很明显，我们需要反转node=2和node=1， 即 node.next.next=node; 同时 node.next=null;
    所以，这个问题就可以是：F(node=1)=F(node=2)+ 反转node=2和node=1

  • 递归代码：

    public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) {  //终止条件并不难想
                return head;
            }
            ListNode node = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return node;  //按上面的例子，F(node=1)和F(node=2)它俩反转后的头节点是同一个
    }