目录
一.反转整个链表
二.反转链表前 N 个节点
三.反转链表的一部分(区间范围)
四.K个一组反转链表
一、反转整个链表
1.方法一:迭代反转单链表
/*****反转以a为头结点的链表(双指针向前推进)******/
ListNode reverse(ListNode head){
ListNode pre, cur, next;
pre = null; cur = head; next = head;
while(cur != null){
next = cur.next; // 暂存cur的下一个节点
cur.next = pre; // 反转
// pre,cur指针向后移动
pre = cur;
cur = next;
}
return pre; // 返回反转后的头结点
}
2.方法二:递归实现反转单链表
/****定义,将以[head为起点]的链表反转,并返回反转之后的头结点*****/
ListNode reverse(ListNode head){
// 1.递归终止:链表只有一个节点,反转它自己
if (head.next == null) return head;
// 2.递推
// (假装head.next后面都反转)返回反转之后的头结点,所以last作为结果返回
ListNode last = reverse(head.next);
head.next.next = head; // 此时只剩下head没反转,这里是对head和(head.next)进行反转操作
head.next = null;
return last;
}
注意事项
1.递归函数的base case出口,if(head.next == null) return head;链表只有一个节点的时候,反转是它自己,直接返回它自己即可
2.当链表递归反转之后,新的头结点为last,那么之前的head变成了最后一个节点,别忘了把head反转后变成末尾,此时末尾需要指向null,也就是head.next = null
二、反转链表前 N 个节点
代码
/****定义,将以[head为起点]的链表反转N个节点,并返回反转之后的头结点*****/
后继节点
ListNode successor = null;
ListNode reverseN(ListNode head,int n){
// 1.递归终止:链表只有一个节点,反转它自己
if (N == 0) {
// 存储后继节点(第n+1节点),便于将两段节点连接起来
successor = head.next;
return head;
}
// 2.递推
// 以head.next为起点,需要反转前n - 1个节点
ListNode last = reverse(head.next,n - 1);
head.next.next = head; // 此时只剩下head没反转,将head和(head.next)以后的节点连接起来
head.next = successor;
return last;
}
分析:与[一、反转整个链表]具体的区别
(1)base case递归出口变成了n == 1,因为如果反转一个元素那么返回本身,同时记录后继节点
(2)刚刚我们直接把head.next为null,那么因为我们反转整个链表,而反转前N个链表head不一定是最后一个了,所以一定要记录后继节点successor(第n+1个节点),反转之后将head和[未反转部分]连接上
三、反转链表的一部分(区间范围)
代码
ListNode reverseBetween(ListNode head, int m, int n){
// 1.递归出口,base case
if (m == 1) return reverseN(head,n); // 反转前n个元素
// 2.前进到反转起点触发base case
head.next = reverseBetween(head.next, m - 1, n - 1)
return head;
}
给一个索引区间[m,n]（索引从 1 开始），仅仅反转区间中的链表元素
(1)若m == 1的话,那不就是反转前n个元素嘛
(2)若m != 1的话,如果我们把head的索引视为1,那么我们从第m个开始反转
如果我们把head.next索引视为1,那么我们相对head.next节点,从第m-1个元素开始反转
head.next.next索引视为1,那么我们相对head.next.next节点,从第m-2个元素开始反转
直到m-2 == 1触发base case,那么就转为成了[反转前n个元素的问题,可以求出解了]
四 、K个一组反转链表
代码
ListNode reverseKGroup(ListNode head, int k){
// 1.递归出口
if (head == null) return null;
// 检测是否有足够K个节点构成一组进行反转操作
ListNode a, b;
a = b = head;
for (int i = 0;i < k; i++){
// 不足k个,不需要反转,base case
if (b == null) return head;
b = b.next;
}
// 反转前k个元素
ListNode newHead = reverse(a,b);
// 2.递推:递归反转后后续链表并连接起来
head.next = reverseKGroup(b,k);
return newHead;
}
分析
(1)reverseKGroup(head,2),以2个节点为一组反转链表,若我们把前2个节点反转,那么后面的节点需要怎么处理?
递归特征:缩小问题,重复子问题,我们发现后面的节点也是一条链表,而且规模比原来的链表小,也是再把前2个节点先反转,这就是子问题
五、总结
(1)链表是一种"兼具递归"和"迭代性质"的数据结构,但注意,递归链表并不高效,和迭代解法相比,时间复杂度都是O(N)
(2)但是迭代解法是O(1),递归解法需要O(N),因为递归需要堆栈,空间复杂度是O(N),考虑效率还是迭代法
