题目
思路
这一题可以考虑先学习下递归问题前置知识和解题思路,这里就直接说了
- 定义递归函数的作用以及返回值
ListNode reverseList(ListNode head)
这个函数的作用是将以head 为头节点的链表给反转,并返回反转后链表的头节点。 -
边界条件
任何一个递归函数都会有出口,否则就会陷入无穷的递归,最后导致栈溢出。
这里的边界就是:- head ==null 空链表,反转后还是 null
- head.next==null 链表只有一个节点,反转后还是自己。
以上两种情况下,都只用返回 head 即可。
-
本层处理和递归进入下一层
对于这一层,我们递归函数要做什么。然后递归向下处理剩余的部分。
不过这一题的话,我们是先递归处理剩下的部分,也就是先将头节点之后的链表给翻转了。再进行头节点的引用对象的转移。
如下图:
Code
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode newHead=reverseList(head.next);
head.next.next=head;
head.next=null;
return newHead;
}
}