反转链表

参考：公众号labuladong

反转整个链表 - 递归

对于递归算法，最重要的就是明确递归函数的定义。
reverse 函数定义：输⼊⼀个节点 head ，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
以head.next为起点进行反转，之后与head连接

这个 reverse(head.next) 执⾏完成后，整个链表就成了这样：

ListNode reverse(ListNode head) {
	//base case:链表只有一个节点
	if(head.next == null) return head; 
	Node last = reverse(head.next);
	head.next.next = head;
	head.next = null;
	return last;
	

}

反转链表前 N 个节点 - 递归

反转过程图

reverseN函数：反转以head为起点的n个节点，返回新的头节点
//使用 couont记录迭代几个节点
以head.next为起点，反转前n-1个节点

1. base case 变为 n == 1 ，反转⼀个元素，就是它本⾝，同时要记录后驱节点n+1，反转之后将 head 连接上。

ListNode successor = null;//后驱节点
Node reverseN(Node head, int n) {//n=3
	if(n==1) {
		//只剩一个节点时,是节点3，要记录它的后驱节点4，之后与反转链表的尾节点1相连
		successor = head.next;
		return head;
	}
	//以head.next为起点，需要反转前n-1个节点
	ListNode last = reverseN(head.next, n-1);
	
	head.next.next = head;
	//让反转之后的head节点和后面的节点连起来
	head.next = successor;
	return last;
}

反转链表的⼀部分 - 递归

给⼀个索引区间 [m,n] （索引从 1 开始），仅仅反转区间中的链表元素。

• 如果 m == 1 ，就相当于反转链表开头的 n 个元素：reverseN(Node head, int n)
• 如果 m != 1 怎么办？
  如果我们把 head 的索引视为 1，那么我们是想从第m 个元素开始反转对吧；
  如果把 head.next 的索引视为 1 呢？那么相对于head.next ，反转的区间应该是从第 m - 1 个元素开始的；
  那么对于head.next.next 呢……

ListNode reverseBetween(ListNode head, int m, int n) {
	// base case
	if (m == 1) {
		return reverseN(head, n);
	}
	// 前进到反转的起点触发 base case
	head.next = reverseBetween(head.next, m - 1, n - 1);
	return head;
}

K 个⼀组反转链表

反转整个链表 - 迭代

// 单链表节点的结构
public class ListNode {
	int val;
	ListNode next;
	ListNode(int x) { val = x; }
}

//反转
//以a为头结点的整个链表
ListNode reverse(ListNode a){
	ListNode cur, pre, next;
	pre = null; cur= a; next = a;//cur,next初始化为a
	while(cur! = null){
		next = cur.next;
		//逐个结点反转
		cur.next = pre;
		//更新指针位置
		pre = cur;
		cur = next;
	}
	//返回反转后的头结点
	return pre;
}

反转 a 到 b 之间的结点 - 迭代

「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」，
那么如果让你「反转 a 到 b 之间的结点」？只要更改函数签名，并把上⾯的代码中 null 改成 b 即可
反转区间 [a, b) 的元素，注意是左闭右开

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
	ListNode pre, cur, nxt;
	pre = null; cur = a; nxt = a;
	// while 终⽌的条件改⼀下就⾏了
	while (cur != b) {
		nxt = cur.next;
		cur.next = pre;
		pre = cur;
		cur = nxt;
	}
	// 返回反转后的头结点
	return pre;
}

K 个⼀组反转链表

发现递归性质：
对这个链表调用reverseKGroup(head, 2)，以2个节点为一组反转链表：

如果我设法把前 2 个节点反转，那么后⾯的那些节点怎么处理？后⾯的这些节点也是⼀条链表，⽽且规模（⻓度）⽐原来这条链表⼩，这就叫⼦问题

我们可以直接递归调⽤ reverseKGroup(cur, 2) ，因为⼦问题和原问题的结构完全相同，这就是所谓的递归性质。
发现了递归性质，就可以得到⼤致的算法流程：

1、先反转以 head 开头的 k 个元素。

2、将第 k + 1 个元素作为 head 递归调⽤ reverseKGroup 函数。

3、将上述两个过程的结果连接起来。

思路

结果

ListNode reverseKGroup(ListNode head, int k){
	if(head == null) return null;
	//区间[a,b) 包含k个待反转元素
	ListNode a, b;
	a = b = head;  //a和b在head处
	for(int i = 0; i < k; i++){
		//base case：不足k个，不需要反转
		if(b == null) return head;
		b = b.next;
	}// k=2时，b来到第3个
	
	//反转前k个元素， 此时a和b形成一个区间:反转区间[a,b)
	ListNode newHead = reverse(a, b);
	//递归反转后续链表，并连接起来
	a.next = reverseKGroup(b,k);
	return newHead;
}

注

• 链表是⼀种兼具递归和迭代性质的数据结构
  对于链表题，先画图画步骤 ，看清节点的改变顺序：初始图，最终效果图，以head.next为起点反转图，重新连接图
  别忘了链表的末尾要指向 null
  反转时： 链表节点位置不变，指针方向和连接变了

• 对于递归算法，最重要的就是明确递归函数的定义
  不要跳进递归（你的脑袋能压⼏个栈呀？），⽽是要根据递归函数定义，来弄清楚这段代码会产⽣什么结果：
  先写递归的base case;
  具体反转时： 以head.next为起点进行反转，之后与head连接;

• 递归是整体的思路，迭代是一步一步的
  递归操作链表并不⾼效。和迭代解法相⽐，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，⽽递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和⼩伙伴装逼，但是考虑效率的话还是使⽤迭代算法更好