题目描述

输入一个链表,反转链表后,输出新链表的表头。

最开始的思路是保存链表中的每一个值到一个数组中,然后逆序输出到新链表中,暴力反转链表。实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public ListNode ReverseList(ListNode head) {
ArrayList<Integer> array = new ArrayList<>();
ListNode cur = head;
ListNode pre, result = new ListNode(0);
pre = result;

if(head == null){
return result;
}

while(cur != null){ //循环读取链表数值,存在array链表中
array.add(cur.val);
cur = cur.next;
}

for(int i = array.size() - 1; i >=0; i--){
pre = new ListNode(array.get(i));
pre = pre.next;
}

return result.next;
}
}

想法很美好,现实很骨感。运行时报出如下错误:

Exception in thread “main” java.lang.NullPointerException

咋肥事,还会有空指针报错?马上Debug,发现一个漏洞。

最开始定义了ListNode pre, result两个新链表,pre用于循环,每次增加新的next节点,因为每次pre.next = new ListNode(num)时,pre.val会赋予新的值,不能成为一条完整的逆序链表,因此定义了result链表来与pre每次添加的值相等,因为result = pre,因此两个内存地址相等,也就是result每次会以链表形式添加pre所添加的新元素,从而达到逆序操作。

不过问题就出在pre = new ListNode(array.get(i));这上,每次new一个值时,pre的内存地址就改变一次,但是result的内存地址不会变,因此result不会与pre产生联系,也就是最后return result的时候,result的值在最开始定义result时就已经确定了,与后续pre的操作无关,因此无法得到反转链表的目的。

所以上述代码是些辣鸡。那就换个思路吧,直接从链表本身入手。实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
ListNode pre = null;
ListNode next = null;
while(head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}

啥意思呢,pre表示所给链表的前一个节点,next表示所给链表的下一个节点。代码解释如下:

  1. next = head.next 表示next保存head的下一个节点,保证head.next不会丢失
  2. head.next = pre 表示head指向了pre,也就是head从后指向前
  3. pre = head 表示pre现在已经是在next前面的数值中,由后指向前的一个链表;
  4. head = next 表示head找回原先的head的下一节点,也就是第一步中被next保存的节点;
  5. 继续以上操作,直至head遍历完成,此时pre也反转完成。

举个栗子最直观:

输入链表 1->2->3->4->5

  1. next = head.next = 2->3->4->5
  2. head.next = pre =null
  3. pre = head = 1
  4. head = next = 2->3->4->5
  5. —新一轮循环—
  6. next = head.next = 3->4->5
  7. head.next = pre = 1 (此时head.val = 2,因此head 表示2->1
  8. pre = head = 2->1 (达到反转的目的
  9. head = next = 3->4->5
  10. —新一轮循环—
  11. ……
  12. head = null
  13. pre = 5->4->3->2->1

输出链表 5->4->3->2->1

任务完成,值得品味。