题目描述
输入一个链表,反转链表后,输出新链表的表头。
最开始的思路是保存链表中的每一个值到一个数组中,然后逆序输出到新链表中,暴力反转链表。实现如下:
1 | class Solution { |
想法很美好,现实很骨感。运行时报出如下错误:
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 | public class Solution { |
啥意思呢,pre表示所给链表的前一个节点,next表示所给链表的下一个节点。代码解释如下:
- next = head.next 表示next保存head的下一个节点,保证head.next不会丢失;
- head.next = pre 表示head指向了pre,也就是head从后指向前;
- pre = head 表示pre现在已经是在next前面的数值中,由后指向前的一个链表;
- head = next 表示head找回原先的head的下一节点,也就是第一步中被next保存的节点;
- 继续以上操作,直至head遍历完成,此时pre也反转完成。
举个栗子最直观:
输入链表 1->2->3->4->5
- next = head.next = 2->3->4->5
- head.next = pre =null
- pre = head = 1
- head = next = 2->3->4->5
- —新一轮循环—
- next = head.next = 3->4->5
- head.next = pre = 1 (此时head.val = 2,因此head 表示2->1)
- pre = head = 2->1 (达到反转的目的)
- head = next = 3->4->5
- —新一轮循环—
- ……
- head = null
- pre = 5->4->3->2->1
输出链表 5->4->3->2->1
任务完成,值得品味。