数据结构与算法总结之递归反转单链表
-
单链表节点的结构:
public class ListNode { int val; ListNode next; ListNode(int x){val = x;} }
反转整个链表
ListNode reverseLinkedList(ListNode head){ // base case:只有一个节点就返回那个节点 if(head.next==null){ return head; } ListNode last = reverseLinkedList(head.next); // 反转箭头 head.next.next = head; // 头节点的next置空 head.next = null; // 最后一个节点变成头节点 return last; }
反转前n个节点
反转前n个节点与反转整个链表的区别是需要记录第n个节点的下一个节点node,然后将
head.next
设置为node即可。public class ReverseLinkedList{ // 记录第n个节点的下一个节点 ListNoe lastNext = null; ListNode reverseFirstN(ListNode head,int N){ if(N==1){ lastNext = head.next; return head; } ListNode last = reverseFirstN(head.next,N-1); head.next.next = head; head.next = lastNext; return last; } }
反转区间[m,n]部分的链表
1<=m<=n<=链表长度
与反转前n个节点其实是一样的,只是需要找到第m个节点作为递归的头节点,并将第m-1个节点的下一个节点置为last即可。
public class ReverseLinkedList{ // 记录第n个节点的下一个节点 ListNoe lastNext = null; ListNode reverseBetween(ListNode head,int m,int n){ if(m==1){ return reverseFirstN(head,n); } // ListNode last = reverseBetween(head.next,m-1,n-1); // head.next = last; head.next = reverseBetween(head.next,m-1,n-1); } }
-
@fantasticpsq 由浅入深挺好
-
见解独特,理解深刻
-
讲的很好呀!