反转链表

关于链表反转

一、整个链表的反转

说明：

输入: 1 ->2 ->3 ->4 ->5 ->null
输出：null <-1 <-2 <-3<- 4 <-5 

先给出其代码吧

ListNode reverse(ListNode head){
	if(head==null || head.next==null)      return head;
	ListNode next=reverse(head.next);
	head.next.next=head;
	head.next=null;
	return next;
}

释义:
输入一个结点head，将 [以head为起点]的链表进行反转，并且返回反转之后的头结点

那么输入 reverse(head) 后，会在这里进行递归：
ListNode last=reverse(head.next) 可以 理解为，见下图 :

当 reverse(head.next)执行完之后，整个链表就会变成:

此外， reverse 反转之后的头结点，就会被我们用变量 last 接收了

• 关于head.next.next=head;

之后：

head.next=null;
  return last;

这样，就完成了单链表的反转，值得注意的是***每次 `reverse()` 函数会返回反转之后的头结点！*** ---

二、进阶 反转前N个节点

例如我们来实现这样的一个函数

//将链表的前n 个节点反转（n<= 链表长度）
  ListNode reverseN(ListNode head,int n)

这需要对之前的代码稍加修改：

ListNode successor=null;   //后驱节点
// 反转以 head 为起点的 n 个节点，返回 新的头节点。
ListNode reverseN(ListNode head,int n){
	if(n==1){
		successor=head.next;
		return head;
	}
	ListNode last=reverseN(head,n-1);
	head.next.next=head;
	head.next=successor;
	return last;
}

之前我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

---

三、再进阶 反转链表中的一部分

我们现在来解决对于一个链表中，索引区间在[m,n] 之间的部分进行反转ListNode reverseBetween(ListNode head,int m,int n) 首先，如果 m==1 ,就相当于反转链表开头的 n 个元素，也就是：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
     	return reverseN(head,n);
     }
     // ....
  }

那么当m!=1 时呢？ 如果我们把head 的索引视为 1 ，那么是要从第m 个元 素开始反转，索引我们可以将head.next 的索引视为 1 时，那么反转区间相对应的就是从 第 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,m-1,n-1);
    return head;
}