反转链表
算法思想
初始条件,头结点不能为null,否则直接返回null
对于第i个节点,我们只要得到第i+1到last节点的逆序链表。假设第i+1到last节点的逆序链表的最后一个元素叫prev,那我们只要把prev.next设置为当前节点,并返回当前节点即可
对于最后一个节点last,last.next是null,我们直接返回last即可
以上三步可以逆序,但我们好像没保存新的头结点(原来的尾节点),第三部保存一下即可
上代码
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
protected ListNode newHead;
public ListNode ReverseList(ListNode head) {
if(head == null){
return null;
}
ListNode last = ReverseListRecursive(head);
last.next = null;
retur...