Reverse Link List Recursion
Reverse a linked list using recursion.
Example :
Given 1->2->3->4->5->NULL,
return 5->4->3->2->1->NULL.
Solution:
Time: O(n)
Space: O(1)
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
// 1->2->3->4->5
// 1<-2<-3<-4<-5
public ListNode reverseList(ListNode A) {
if (A == null || A.next == null) return A;
ListNode newHead = reverseList(A.next);
A.next.next = A;
A.next = null;
return newHead;
}
}