【每日一题】- 2019-08-30 - 链表的分组逆序 about leetcode HOT 4 CLOSED

/**
 * 思路，
 * 进去首先遍历一遍单链表，给每个元素加上preNode属性，表示前置结点，最后用一个变量记录尾结点
 *
 * 接下来的循环次数，应该是paseInt(len/K) + len%K
 * 分成两段：
 * 第一段循环：构造包含K个结点的逆序链表段，并拼接它们
 * 第二段循环：构造包含1个结点的逆序连标段，并拼接它们
 * 
 * @param {*} head
 * @param {*} K
 * @returns
 */
function reverseLinkedArray(head, K) {
	var len = 0;// 单链表长度
	var nowNode = head,
		preNode = null,
		tailNode = null;
	while (nowNode) {
		nowNode.preNode = preNode;
		preNode = nowNode;
		if (nowNode.next == null) {
			tailNode = nowNode;
		}
		nowNode = nowNode.next;
		len++;
	}

	var finalLinkHead = null;
	for (var i = 0, count = parseInt(len / K); i < count + (len % K); i++) {
		var j = i >= count ? 1 : K;
		var newHead = new ListNode();
		var tHead = newHead;
		while (j > 0) {
			tHead.val = tailNode.val;
			tHead.next = new ListNode();
			tailNode = tailNode.preNode;
			if (j == 1) {
				break;
			}
			tHead = tHead.next;
			j--;
		}
		tHead.next = finalLinkHead;
		finalLinkHead = newHead;
	}

	return finalLinkHead;
}

function ListNode(val) {
	this.val = null;
	this.next = null;
}

function iterateLink(link) {
	var array = [];
	while (link) {
		array.push(link.val);
		link = link.next;
	}
	return array;
}

function demo(array, K) {
	var head = new ListNode();
	var nowNode = head;
	for (var i = 0; i < array.length; i++) {
		nowNode.val = array[i];
		if (i == array.length - 1) break;
		nowNode = nowNode.next = new ListNode();
	}

	console.log(iterateLink(reverseLinkedArray(head, K)));
}

var timestart = new Date().getTime();
demo([1, 2, 3, 4, 5, 6, 7, 8], 3);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8], 2);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 1);
demo([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3);
demo([0, 1], 1);
console.log("use time = ", new Date().getTime() - timestart);

function reverse(arr,k){
	var len = arr.length;
	var num = len % k;
	for(var i = num; i< len; i = i+k){
		swap(i);
	}
	function swap(i){
		var temp , begin = i, end = i+k-1;
		while(end - begin > 0){
			temp = arr[begin];
			arr[begin] = arr[end];
			arr[end] =temp;
			begin ++
			end --
		}
	}
	return arr;
}