算法思想
- 初始条件,头结点不能为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;
return newHead;
}
public ListNode ReverseListRecursive(ListNode node) {
if(node.next != null){
ListNode prev = ReverseListRecursive(node.next);
prev.next = node;
return node;
}else{
newHead = node;
return node;
}
}
}
前来学习,帮顶哦