题目
要求
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
答案
这道题目也是使用虚拟节点,我先使用虚拟节点做了一遍,结果如下,就是想清楚在循环的时候保留当前节点就可以:
public static ListNode reverseList(ListNode head) {
ListNode virtual = new ListNode(0);
while (head != null) {
// 先保留当前节点
ListNode virtualNode = head;
// 更换头指针
head = head.next;
// 更换虚拟节点的下个节点
virtualNode.next = virtual.next;
// 维护外围虚拟节点
virtual.next = virtualNode;
}
return virtual.next;
}
官方题解的递归思路有点烧脑,我看了半天没看懂,然后 debug 看了一下才明白:
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode temp = reverseList2(head.next);
head.next.next = head;
head.next = null;
return temp;
}
递归思路我能看懂 ListNode temp = reverseList2(head.next);
,看不懂的是head.next.next = head;
和 head.next = null;
,下面举例说明:原始的链表是 1→2→3→4→5→null.
现在递归,到最后一个节点返回,这个时候 temp 是 5,head 是 4,在执行完 head.next.next = head;
之后,其实修改的是 5 节点,也就是修改完之后,temp 的内容为 5→4→5→4····
,执行完 head.next = null
之后,temp 的结果为 5→4→nul
。
现在看看继续倒数第二轮,这个时候 temp 为 5→4→null
,head 为 3→4→null
,执行完 head.next.next = head;
其实就是修改了 4 节点,把 4 的 next 修改为 3,结果为 3→4→3→4→3······
,注意,这个时候 temp 为 5→4→3→4→3→······
,执行完 head.next = null;
之后,temp 的结果为 5→4→3→null
,由此可以看出规律来。
其实在每一次执行完 head.next.next = head;
之后都会形成一个环,下一个head.next = null;
就是为了破除环,其实这块有一个对象引用的问题需要熟悉了解,head.next.next 其实修改的是 temp 的尾节点,head.next 是在前一个基础上修改 temp 的尾节点的 next 为 null,避免出现了环。这个确实不太好理解,debug 看更清楚一点。