题解 | #反转链表#
反转链表
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode head) { // write code here if(head == null){ return null; } ListNode pre = null; ListNode nxt = null; while(head != null){ nxt = head.next; head.next = pre; pre = head; head = nxt; //pre = pre.next;//wrong //head = head.next; } ListNode res = pre; return res; } }
记录一下错误思路,大体就是遍历应在原链表,不应在新链表上。
含有伪代码的解释:
声明pre,nxt = null
原:pr head nxt
空 头节点 空
nxt = head.next;
pr head-> nxt
空 头 原头后1
head.next = pre
pr <- head nxt
新头后1 头 原头后1
之后遍历整个链表就行了,注意,是按照原链表的顺序进行迭代,去操作链表反转,先前已经处理过第一个头节点了,下一步要处理头节点后面的节点,也就是之前存的 nxt = head.next
pre = head;
head = nxt;
不能想当然地
pre = pre.next;
head = head.next;
因为链表已经改变,它在头节点处断开了,
比如
1->2->3->4->5在处理完第一次
nxt = head.next; head.next = pre;
时已经变成了
null<-1 2->3->4->5
pre = null; nxt = 2;
这样的话pre.next 和head.next除了前两次是null不能正常遍历之外,即使能遍历也是向相反方向,是不对的。