[数据结构与算法]递归翻转链表

迭代的关键

• pre，cur，next 分别指向需要翻转的区间的 前一个节点，当前操作的节点，下一个节点

递归的关键

• 确定递归函数的 输入值，功能，返回值，边界条件，而不是跳入递归函数里面一个个分析（你的脑子里能承受几个函数压入栈的分析？）

反转链表

• 剑指 Offer II 024. 反转链表
  • head.next.next = head，是为了让当前节点的下一个节点的next指向当前节点
  • head.next = null，则是为了反转链表后头节点的next指向 null（变尾节点了）

	// 以head为起始节点的链表进行反转，返回反转后的起始节点
	function reverseList(head) {
		if (!head || !head.next) return head;
		let last = reverseList(head.next);
		// 每次反转两个节点
		head.next.next = head;
		head.next = null;
		return last;
	}

反转链表的前n个节点

• 边界条件 需要 结合n 来判断
• 反转后头节点变为该部分的尾节点（因为不一定反转整个链表），所以需要 记录第n+1个节点，并让它的next指向它

	// 反转以head为起始节点的前n个节点，返回反转后的起始节点
	let successor = null;
	function reverseN(head,n) {
		if (!head || n == 1) {
			successor = head.next;
			return head;
		}
		let newHead = reverseN(head.next,n - 1);
		head.next.next = head;
		head.next = successor; 
		return newHead;
	}

反转链表的一部分

根据区间进行反转

• 反转链表 ||
  • 若 left 为1，等价于反转链表的前right个节点，不需要反转的链表部分，无须处理

	// 1 <= left <= right <= 链表长度
	@return: { 反转链表后的头节点 } 
	var reverseBetween = function(head, left, right) {
		// 需要翻转部分
		if (left == 1) {
			return reverseN(head,right);
		}
		// 不需要翻转部分
		head.next = reverseBetween(head.next,left - 1,right - 1);
		return head;	
	};

根据头，尾指针进行反转

	var reverseByPointer = function (head,tail) {
		// 转成单链表反转题
		if (head == tail) return head;
		else if (!head || !tail) return null;
		
		let pre = null;
		while (head != tail) {
			let next = head.next;
			
			head.next.next = head;
			head.next = pre;
			
			head = next;
		}
		return tail;
	}

25. K个一组反转链表

• 25 . K 个一组反转链表
  • reverseByPointer：负责反转头节点为head，尾节点为tail的链表部分，返回新的头节点和尾节点
  • 用一个 hair节点 来连接头节点，并注意每次翻转链表后需要去修改个别节点即可

	var reverseByPointer = function(head,tail) {
	    let prev = tail.next;
	    let p = head;
	    while (prev != tail) {
	        let next = p.next;
	        p.next = prev;
	
	        prev = p;
	        p = next;
	    }
	    return [tail,head];    
	};
	var reverseKGroup = function(head, k) {
	    let hair = new ListNode(-1);
	    hair.next = head;
	    let pre = hair;
		// 时间复杂度：O(n*n)
	    while (head) {
	        // 记录分区的head，tail节点
	        let tail = pre;
	        for (let i = 0; i < k; i ++) {
	            tail = tail.next;
	            if (!tail) return hair.next;
	        }
	
	        let next = tail.next;
	        [head,tail] = reverseByPointer(head,tail);
	        pre.next = head;
	        tail.next = next;
	
	        pre = tail;
	        head = tail.next;
	    }   
	    return hair.next;
	};

• 转换成找到每个k区间的头节点进行 reverseN 翻转，注意下标即可

	let succ = null;
	var reverseN = function(head,N) {
	    if (!head) return head;
	    if (N == 0) {
	        // 记录N+1个节点
	        succ = head.next;
	        return head;
	    }
	    let newHead = reverseN(head.next,N - 1);
	    head.next.next = head;
	    head.next = succ;
	    return newHead;
	};
	var reverseBetween = function(head,left,right) {
	    if (left == 0) {
	        return reverseN(head,right);
	    }
	    head.next = reverseBetween(head.next,left - 1,right - 1);
	    return head;
	};
	var reverseKGroup = function(head, k) {
	    // [1,链表长度]
	    // 统计链表的长度
	    let node = head;
	    let len = 0;
	    while (node) {
	        len ++;
	        node = node.next;
	    }
	    // 循环翻转区间
	    let newHead = null;
	    // 时间复杂度：O(n / k * )
	    for (let start = 0,j = 1;(j * k - 1) < len; start += k,j ++) {
	        if (start == 0) {
	            // 0 ~ (k - 1)
	            newHead = reverseN(head,k - 1);
	        } else {
	            // k ~ (2k - 1)，2k ~ (3k - 1)等
	            reverseBetween(newHead,start,j * k - 1);
	        }
	    } 
	    return newHead;
	};