关于反转单链表的问题

Question

leetcode 206. 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

递归解法如下：

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

问题1：在调试过程中，为什么当执行到

 head.next.next = head;

时会报内存溢出错误？如图所示

问题2：这整个执行方法中，都是对head进行操作：

   head.next.next = head;
   head.next = null;

并没有对p进行赋值操作，为什么return p 就能获得反转链表的值？

麻烦老师解答一下，非常感谢！

Answer 1

liuyubobobo 2019-07-17 00:51:29

1. 

我测试了一下，在本地运行没问题，本地调试在这句话确实会顿很长时间，但在我的机子上不会报错，可以继续下去。我不确定其他环境会怎样。

由于运行没问题，debug有这个问题，我倾向于认为是IDE的问题，所以你需要去jetbrains官网讯问原因和解决方案。

2.

public ListNode reverseList(ListNode head)

这个函数的语义是，翻转以head为头结点的链表，返回翻转后的头结点。

所以，返回值p是翻转链表的头结点，这个头结点已经不需要动了，关键是处理原来的头结点head，因为现在head成为了尾结点，他的next是不对的。

在我提供的这个代码中，有两句注释，看能不能帮助你理解：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0206-Reverse-Linked-List/java-0206/src/Solution2.java

强烈建议使用课程中5-5小节的方式，用纸笔一步一步去模拟一下，看一下算法的整个过程，每一步每一个节点的next在怎么变。可以先看只有两个节点的情况，再看只有三个节点的情况。

加油！：）

• 提问者 那条时光流过的小巷 #1

  非常感谢老师的帮助！

Answer 2

提问者 那条时光流过的小巷 2019-07-17 09:54:27

在执行完if return head后，进入如图所示断点：此时内存地址与值如下所示：

再往下执行

head.next.next = head;

之后，内存地址如下图所示

此时的head 与 p 都存储了一个无限内部循环的 next。

这里我不太清楚发生了什么？

• 提问者 那条时光流过的小巷 #1

  但是此时p的内存地址是ListNode@489；
  head.next的内存地址也是ListNode@489；
  说明我对head.next.next = head;操作，就是再对P进行操作；
  P随着head.next.next = head;的执行
  值也发生变化了。

• 提问者 那条时光流过的小巷 #2

  补充：我传的数组是 ｛2 ， 1｝

• liuyubobobo 回复 提问者 那条时光流过的小巷 #3

  因为如果不debug直接运行没有问题，debug却产生这个问题，这是我倾向于认为是IDE的问题的原因，和你的逻辑无关。是debug单步跟踪造就了这个问题。

Answer 3

提问者 那条时光流过的小巷 2019-07-17 08:26:29

// 以当前节点为头结点的链表信息字符串
@Override
public String toString(){
    StringBuilder s = new StringBuilder();
    ListNode cur = this;
    while(cur != null){
        s.append(cur.val + "->");
        cur = cur.next;
    }
    s.append("NULL");
    return s.toString();

问题补充：

经调试发现，当重写的toString为以上函数时，就会报内存溢出错误，但如果去掉该toString，就不会报错。

• liuyubobobo #1

  对，你的报错说明已经显示了是在toString出的问题，但我不知道这段代码debug为什么会触碰toString，为什么会内存溢出。我倾向于认为是IDE的问题：）

• 提问者 那条时光流过的小巷 #2

  但此时IDE中的Debug时就不显示值了，只显示内存地址。