单链表反转问题

Question

老师您好，在读算法实现代码时有些地方实在看不懂，麻烦解答下，谢谢。

/**
 * 递归，在反转当前节点之前先反转后续节点
 */
public static LinkedNode Reverse1(LinkedNode head) {
   // head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
   if (head == null || head.getNext() == null) {
      return head;// 若为空链或者当前结点在尾结点，则直接还回
   }
   LinkedNode reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()。//先反转当前结点的后续结点。这里为什么赋值给reHead呢？？？？？是不是通过递归从最后一个结点到第一个结点，依次把这些结点赋值给reHead?？？？reHead表示新链表的头结点
   head.getNext().setNext(head);// 将当前结点的指针域指向前一结点。这里为什么要指向前一结点呢？？？？？不是应该指向后续结点吗？？？？？
   head.setNext(null);// 前一结点的指针域令为null?????是不是指新链表中尾结点next=null;
   return reHead;// 反转后新链表的头结点
}

Answer 1

liuyubobobo 2019-09-03 02:53:59

Reverse 的语义是：翻转以 head 节点为头结点的链表，并返回翻转后链表的头结点。所以，对head.next进行翻转，翻转后的新的头结点，也是对 head 翻转翻转后的头结点，存储给 rehead，最终作为返回结果。

剩下的任务是处理head，因为head.next以已经反转好了，但是head还没有动。head.next还连接着原来的节点，但是，原来的节点，现在已经是对head.next进行翻转后新链表的尾结点了。所以，要让这个尾结点的next是现在的head。这就是head.next.next = head 的意思。

最后，现在，head已经是翻转后链表的尾结点了。他的next应该是空。

继续加油！：）

• 提问者 我有明珠一颗 #1

  非常感谢！