LeetCode题解链表的分组逆序

给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每K个节点之间为一组进行逆序,并且从链表的尾部开始组起,头部剩余节点数量不够一组的不需要逆序。(不能使用队列或者栈作为辅助)

例如:

链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8,3->4->5,1->2各位一组。调整后:1->2->5->4->3->8->7->6->null。其中 1,2不调整,因为不够一组。

原文链接: https://www.jianshu.com/p/3dc5e73ab69c

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

\tvar finalLinkHead = null;
\tfor (var i = 0, count = parseInt(len / K); i < count + (len % K); i++) {
\t\tvar j = i >= count ? 1 : K;
\t\tvar newHead = new ListNode();
\t\tvar tHead = newHead;
\t\twhile (j > 0) {
\t\t\ttHead.val = tailNode.val;
\t\t\ttHead.next = new ListNode();
\t\t\ttailNode = tailNode.preNode;
\t\t\tif (j == 1) {
\t\t\t\tbreak;
\t\t\t}
\t\t\ttHead = tHead.next;
\t\t\tj--;
\t\t}
\t\ttHead.next = finalLinkHead;
\t\tfinalLinkHead = newHead;
\t}

\treturn finalLinkHead;
}

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

function iterateLink(link) {
\tvar array = [];
\twhile (link) {
\t\tarray.push(link.val);
\t\tlink = link.next;
\t}
\treturn array;
}

function demo(array, K) {
\tvar head = new ListNode();
\tvar nowNode = head;
\tfor (var i = 0; i < array.length; i++) {
\t\tnowNode.val = array[i];
\t\tif (i == array.length - 1) break;
\t\tnowNode = nowNode.next = new ListNode();
\t}

\tconsole.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);
```

45码

LeetCode题解求一根绳子被切两刀能组成一个三角形的概率。

如题题解:我们可以设绳长为1,设:- 其中两段长为x, y且x, y都>0- 故第三段长为1-x-y且>0故可以在二维坐标轴画出一个三角形(由x=0;y=0;1-x-y=0围成)要想构成三角形还要满足:- x+y > 1-x-y => x+y > 0.5- x+1-x-y > y => y < 0.5- y+1…

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候,一个真实的面试题,这是一个开放题。题目描述:想办法,将一个城市的所有灯泡数量统计出来。题解:费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里,每套房有灯泡5只,那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡,那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的,具体应…

LeetCode题解黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解:可以用一个相机即可

LeetCode题解圆上任取三点构成锐角三角形的概率

来自字节跳动的一道几何题题解:1/4