/**
*
* 判断一个链表是否有环 【141】
*
*
* 快慢指针，求相遇
*/
var hasCycle = function(head) {
if(!head) return false
let pre = head, cur = head;
while(cur && cur.next) {
pre = pre.next;
cur = cur.next.next;
if(pre === cur) {
return true
}
}
return false
};
/**
*
* 给定一个链表，返回链表开始入环的第一个节点 【142】
*
*
* 快慢指针求相遇
* 假设入环节点距离 头节点的距离为 a； 快慢指针相遇点距离头节点的距离分别为 b 和 c (两个弧长 , b为慢指针走过的圆弧长度),
* 快指针走的长度：a + n(b+C) + c
* 慢指针走的长度：a + b
* 快指针的速度 = 慢指针的2倍 所以距离也是慢指针的2倍
* a + n(b+c) + c = 2(a+b) ---> 导出 a = (n-1)(b+c) + c
* 因为 b + c 等于 环的长度，所以相当于走了很多圈。 实际导出 a = c 即： 入环位置 距离 头节点和 距离 快慢指针相遇节点的 距离相等
* 所以，在相遇节点走c步，头节点也走c步，两个节点相遇的位置即为入口位置
*/
var detectCycle = function(head) {
if (!head) return null;
let pre = head, cur = head;
while(cur && cur.next) {
pre = pre.next;
cur = cur.next.next
if (pre === cur) {
let temp = head;
while(temp != pre) {
temp = temp.next
pre = pre.next
}
return temp
}
}
return null
};
/**
*
* 快乐数
*
**/
var getSum = function(n) {
let sum = 0,cur = 0;
// 从最高位数加到个位数
while( n > 0) {
cur = Math.floor(n%10)
sum = Math.floor(sum + cur**2)
// 换下一位数字
n = Math.floor(n/10)
}
return sum
}
let isHappy = function (n) {
let slow = n;
let fast = getSum(n);
while(fast !== 1 && fast !== slow){
slow = getSum(slow);
fast = getSum(getSum(fast));
}
return fast === 1;
};
console.log(isHappy(4))
/**
*
* 两数相加
*
**/
var addTwoNumbers = function(l1, l2) {
let addOne = 0
let sum = new ListNode('0')
let head = sum
// 如果有进位的话，也是需要运算的
while (addOne || l1 || l2) {
// 需要判断值是否存在，因为可能存在位数不同的情况
let val1 = l1 !== null ? l1.val : 0
let val2 = l2 !== null ? l2.val : 0
let r1 = val1 + val2 + addOne
// 因为数字精度不准确所以需要单独处理
addOne = r1 >= 10 ? 1 : 0
// 只存放个位的数字
sum.next = new ListNode(r1 % 10)
sum = sum.next
if (l1) l1 = l1.next
if (l2) l2 = l2.next
}
return head.next
};
/**
*
* 反转链表
*
*/
// 方法1 pre 和 cur next
var reverseList = function(head) {
// 判断长度
if(head == null || head.next == null) return head
let pre = null;
let current = head;
// 需要声明next变量，来保障反转过后的指向(重新链接起来各个节点)
while(current) {
let currenNext = current.next
current.next = pre
pre = current
current = currenNext
}
return pre
};
// 方法二递归
// 抽象为 head->next 和head->next->next的反转过程
var reverseList = function(head) {
// 判断长度
if(head == null || head.next == null) return head
let node = reverseList(head.next)
head.next.next = head
head.next = null
return node
};
/**
*
* 反转指定位置【m，n】的链表
*
*/
var reverseBetween = function(head, left, right) {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
const dummyNode = new ListNode(-1);
dummyNode.next = head;
let pre = dummyNode;
// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
// 建议写在 for 循环里，语义清晰
for (let i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
let rightNode = pre;
for (let i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步：切断出一个子链表（截取链表）
let leftNode = pre.next;
let curr = rightNode.next;
// 注意：切断链接
pre.next = null;
rightNode.next = null;
// 第 4 步：同第 206 题，反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步：接回到原来的链表中
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
};
const reverseLinkedList = (head) => {
let pre = null;
let cur = head;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
// 穿针引线
var reverseBetween = function(head, left, right) {
const retNode = new ListNode(-1)
retNode.next = head
let leftNodePre = retNode
// leftNode 的前一个节点
for(let i = 0; i < left -1; i++) {
leftNodePre = leftNodePre.next
}
/***
* @name 穿针引线
* @目标 让需要反转的每一个节点都插入到左侧启动的右边
* @param leftNodePre 始终表示开始反转链表前的节点
* @param rightNode 反转链表的头
* @param rightNodeNext 下一个需要反转的节点
*
**/
const rightNode = leftNodePre.next
for(let i = 0; i < right - left; ++i) {
const rightNodeNext = rightNode.next
rightNode.next = rightNodeNext.next
rightNodeNext.next = leftNodePre.next
leftNodePre.next = rightNodeNext
}
return retNode.next
};
/**
*
* 按照k组反转
*
*/
const myReverse = (head, tail) => {
let prev = tail.next;
let p = head;
while (prev !== tail) {
const nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return [tail, head];
}
var reverseKGroup = function(head, k) {
const hair = new ListNode(0);
hair.next = head;
let pre = hair;
while (head) {
let tail = pre;
// 查看剩余部分长度是否大于等于 k
for (let i = 0; i < k; ++i) {
tail = tail.next;
if (!tail) {
return hair.next;
}
}
const nex = tail.next;
[head, tail] = myReverse(head, tail);
// 把子链表重新接回原链表
pre.next = head;
tail.next = nex;
pre = tail;
head = tail.next;
}
return hair.next;
};
/**
*
* 旋转链表
*
*/
var rotateRight = function(head, k) {
if( k=== 0 || !head || !head.next) return head
// 环长度
let listLenth = 1;
// 尾接单
let tail = head;
while(tail.next) {
listLenth++;
tail = tail.next
}
// 成环
let sum = listLenth - k % listLenth
if( sum === listLenth) {
return head
}
tail.next = head
while(sum) {
tail = tail.next
sum--
}
head = tail.next
tail.next = null
return head
};
/**
*
* 从倒数第n个位置删除接单
*
*/
// 强撸法
var removeNthFromEnd = function(head, n) {
let preHead = new ListNode(-1);
preHead.next = head;
let len = 0;
let first = head;
while(first){
len++;
first = first.next;
}
len -= n;
first = preHead;
while(len != 0){
len--;
first = first.next;
}
first.next = first.next.next;
return preHead.next;
};
// 快慢指针
var removeNthFromEnd = function(head, n) {
let preHead = new ListNode(-1);
preHead.next = head;
let fastNode = head
let slowNode = preHead
while(n) {
n = n - 1
fastNode = fastNode.next
}
while(fastNode!=null) {
slowNode = slowNode.next
fastNode = fastNode.next
}
slowNode.next = slowNode.next.next
return preHead.next
};