对于递归算法,最重要的就是明确递归函数的定义 递归操作链表并不高效。和迭代解法相比,虽然时间复杂度都是 O(N),但是迭代解法的空间复杂度是 O(1),而递归解法需要堆栈,空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼,但是考虑效率的话还是使用迭代算法更好。
问题:
1.递归反转整个单链表
function reverse(head){
if(!head.next)return head;
const last = reverse(head.next);
head.next.next = head;
head.next=null;
return last;
}
2.反转链表前n个元素
function reverseN(head,n){
let successor;
return reverse(head,n);
}
function reverse(head,n){
if(n===1){
successor = head.next;
return head;
}
let last = reverse(head.next,n-1);
head.next.next = head;
head.next = successor;
return last;
}
3.反转部分链表
function reverseBetween(head,m,n){
if(m===1){
return reverseN(head.n);
}else{
head.next = reverseBetween(head.next,m-1,n-1);
return head;
}
}