theme: channing-cyan

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

前言

算法一直是考验程序员编程思想的一个重要点,一般来说中小型公司在面试中都不会特意去问这种问题,一般都是借着面试者的回答来往下问,比如涉及到Glide就会问LRUCache,HashMap就会问存储和计算Hash的算法.最近我也看了下LeetCode的一些题目,就来讲解一下自己的思路吧

Code

首先来定义一下实体类

``` public class ListNode { int val = 0; ListNode next;

public ListNode(int data) {
    val = data;
}

} ```

然后创建一个链表

``` public static void main(String[] args) { ArrayList listNodeList = new ArrayList(); for (int i = 0; i < 5; i++) { ListNode listNode = new ListNode(i); listNodeList.add(listNode); if (i != 0 ) { listNodeList.get(i - 1).next = listNode; } }

for (ListNode listNode : listNodeList
) {
    try {
        System.out.println(listNode.toString());
    } catch (Exception e) {
        System.out.println(e.toString());
    }
}

} ```

不用在意细节,只要我们目的达到了不就行了吗,你说对吗,宝贝

然后就是反转细节

public static ListNode rever(ListNode head) { if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }

之前看一篇微信公众号的文章说自己不要代入递归,人的脑袋压不了几个栈,我觉得不应该这么说,即使数据无限大我们也应该压几个方法在脑袋里过一下,把整个流程和细节简单的形成一个印象,下面我用画图的方式来讲解一下我的思路

对了,递归的一个特性就是回溯

比如我们第一个rever方法传递的参数是集合中第一个数据,也就是说他的基础val是0,next的ListNode的val是1;如下图

反转2.png

不要看太后面,主要看我蓝色标注部分就行,你现在只要记住我的传递的数据就是那么多

if (head.next == null) { return head; } 因为链表的特性就是一个节点链接着另一个节点,上面代码就是判断当前节点是不是还有下一个节点,没有就直接返回了,这是递归的一个出口,不设置就无限递归直接报错了

ListNode rever = rever(head.next); 这一句就比较重要的,递归的起始点,将我们一开始传递进来的参数head的next作为参数再次调用自身.

我们一开始传递的ListNode的val是0,他的next的ListNode的val肯定是1.就是上图我蓝色标注的.所以说这个地方的参数ListNode的 val = 1.

走到这个地方之后就会进入新的方法,此时的我们rever的参数head他的val是1了,next指向的ListNode的val是2了.

再次判断传递进来的参数的next是不是null,不是就继续往下走,再次走到 ListNode rever = rever(head.next); 再次进入新的方法,此时方法rever的参数head的val是2了,next指向的ListNode是null.这里我就压3个栈,压多了我直接脑袋冒烟,而且你们会越看越迷糊.

判断后直接return head,也就是直接将当前参数返回过去了.

重点!!!此时递归出口已经触发,开始回溯,我现在将我们压的栈简单的写在下面

第一个栈 //head 的 val = 0,next 指向的 ListNode的 val = 1 public static ListNode rever(ListNode head) { if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }

第二个栈 //head 的 val = 1,next 指向的 ListNode 的 val = 2 public static ListNode rever(ListNode head) { if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; } 第三个栈 //head 的 val = 2,next 指向的 ListNode = null 直接返回 public static ListNode rever(ListNode head) { if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }

就先压三个,理解一下运行流程

此时第三个栈参数head的next指向的ListNode是null,所以直接返回到第二个栈中,因为递归的回溯吗,要回去当时调用你的方法,就相当于搭积木

第三个栈不符合要求,直接return了,我们就相当于消费了这个方法,就需要回到第二个栈中.此时注意这个一行 ListNode rever = rever(head.next); 这个时候已经来到了我们的第二个栈了,第二个栈的参数head 的 val = 1,next 指向的 ListNode 的 val = 2,所以返回的就是我们传递的next数据:val = 2,next = null

然后继续向下执行

head.next.next = head; head.next = null; return rever;

已知head的next指向的ListNode为: val = 2,next = null

经过上面代码第一行的洗礼我们的ListNode发生了变化: val = 2,next = head

现在数据变成了这个样子

但是我们要的可不是双向链表,所以执行第二行 head.next = null; 然后数据就变成了这样

哇!你成功反转了一个节点,此时我们将目光向第三行看齐 return rever; 这一句将我们反转后的数据return了,也代表了第二个栈的消亡.

此时来到了第一个栈,return的ListNode数据为val = 2,next指向的ListNode就是我们上图:val = 1,next = null.

我们接着看代码

ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever;

当前rever数据就是我刚刚说的,我们开始走第二行. head.next.next = head; 记住,这是第一个栈了,我们当时说得,第一个栈的数据是ListNode中val = 0,next指向的ListNode中val = 1,因为第二个栈中的反转,现在指向的ListNode为null了;

head.next等于下面这个