数据结构与算法之链表
有更好的方法或者是有问题想讨论的同学可以评论or私信我，大家一起学习一起进步～
2022/4/2
I.链表环相关
牛客网-在线编程-算法篇-面试必刷top101-链表bm6
1.判断链表中是否有环
-方法1. 使用快慢指针 time: O(n) space: O(1)
定义慢指针slow和快指针fast, slow一次走一步，fast一次走两步。若链表无环，则slow和fast不可能相遇。若slow和fast相遇了，则链表一定有环。具体代码如下，
function hasCycle( head ) {
//corner case, empty linked list has no cycle
if (!head) return false;
//Traverse linked list using two pointers.
let slow = head, fast = head;
//Move one pointer(slow_p) by one and another pointer(fast_p) by two.
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
//If these pointers meet at the same node then there is a loop.
if (slow == fast) return true;
}
//If pointers do not meet then linked list doesn’t have a loop.
return false;
} -方法2.使用哈希表 time: O(n) space: O(n)
定义一个哈希表，每次访问过一个结点我们都把这个结点加入哈希表中，如果新访问的结点已经存在于该哈希表中就说明链表有环。具体代码如下，
function hasCycle( head ) {
// use hashtable, everytime we visited a node, add it into the hashtable
let set = new Set();
while (head != null) {
if (set.has(head)) return true;
set.add(head);
head = head.next;
}
return false;
} 牛客网-在线编程-算法篇-面试必刷top101-链表bm7
2.链表中环的入口结点
-方法1.使用哈希表 time: O(n) space: O(n)
定义一个哈希表，每次访问过一个结点我们都把这个结点加入哈希表中，如果新访问的结点已经存在于该哈希表中就返回该结点。如果遍历完成也没有重复访问的节点就无环，返回null. 具体代码如下，
function EntryNodeOfLoop(pHead)
{
//corner case
if (!pHead) return null;
//hashtable time: O(n) space: O(n)
let set = new Set();
while (pHead != null) {
if (set.has(pHead)) return pHead;
set.add(pHead);
pHead = pHead.next;
}
return null;
} -方法2.使用双指针 time: O(n) space: O(1)
定义一个慢指针一次走一步，一个快指针一次走两步，快指针和慢指针将会在环中某点相遇。设从链表头结点到环入口点到距离为a, 环入口点到相遇点到距离为b, 相遇点到环入口点到距离为c, 如下图所示(图片来源网络，侵删)
慢指针走的距离长度等于——a+b
快指针走的距离长度等于——a+k(b+c)+b, 其中k(k > 0)为快指针走的圈数。就像在环形操场跑步，快指针同学的速度是慢指针同学速度的两倍，那么快指针同学总会在某个点追上慢指针同学，并且此时快指针同学已经比慢指针同学多跑了一圈以上了。
我们知道快指针的速度是慢指针的两倍，相同时间下快指针走过的路程也该是慢指针的两倍，于是可以得到等式：
2(a+b) = a+k(b+c)+b --> a = k(b+c) - b --> a = (k-1)(b+c) + c, k-1 > 0.
所以如果我们让一个指针从起点出发，一个指针从相遇点出发，最后它们一定会相遇在环入口。
代码如下，
function EntryNodeOfLoop(pHead)
{
//corner case
if (!pHead) return null;
let slow = pHead, fast = pHead;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = pHead;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
} II.链表其他题目(剑指offer)
牛客网-剑指offer-知识分类篇-数据结构-链表jz6
3.从尾到头打印链表 time: O(n) space: O(n) 太简单不说了
牛客网-剑指offer-知识分类篇-数据结构-链表jz24
4.反转链表
-方法：先对原链表作头结点删除操作，再对新链表作头结点插入操作。代码如下，
function ReverseList(pHead) {
let prev = null, curr = pHead;
while (curr != null) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
} 牛客网-剑指offer-知识分类篇-数据结构-链表jz52
5.两个链表的第一个公共结点
-方法：两个链表若是有公共结点且链表长度不相等，那么让长链表先把差值走了，短链表再开始走，就会碰到公共结点。代码如下，
function FindFirstCommonNode(pHead1, pHead2)
{
//corner case
if (pHead1 == null || pHead2 == null) return null;
let p1 = pHead1, p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
if (p1 == p2) break;
//pHead2 is longer, let it to walk first
if (p1 == null) p1 = pHead2;
//pHead2 is longer, let it to walk first
if (p2 == null) p2 = pHead1;
}
return p1;
} 2022/4/3
牛客网-剑指offer-知识分类篇-数据结构-链表jz52
6.链表中倒数最后k个结点
-方法1：先遍历一遍链表，计算出它的长度存入length变量。于是现在倒数第k个结点就是正数第(length - k)个结点。这里k可能大于length, 可能等于length, 也可能小于length. 当k大于length时，链表中不存在该结点，返回null; 当k等于length时，倒数第k个结点恰好是链表第一个结点，返回pHead; 当k小于length时，结点存在于链表中的(length - k)位置，遍历(length - k)次链表，然后返回剩余链表元素。代码如下，
function FindKthToTail( pHead , k ) {
// conrner case
if (pHead === null || k === 0) return null;
// count the length of the linked list
let length = 0, p = pHead;
while (p) {
length++;
p = p.next;
}
// traverse the linked list by (length - k) times
let times = length - k;
if (times < 0) {
return null;
} else if (times === 0) {
return pHead;
} else {
while (times > 0) {
pHead = pHead.next;
times--;
}
return pHead;
}
} -方法2：思路与方法1相同，不过是不计算链表长度，直接遍历k次，剩余元素数量即为正序遍历次数。复制链表pHead, 然后遍历(k - 1)次该复制链表。最后(复制链表的剩余元素数量 - 1)则为正序遍历次数。代码如下，
function FindKthToTail( pHead , k ) {
//corner case
if (pHead == null || k == 0) return null;
let node = pHead;
//traverse the linked list by k times, and the length of the left linked list will be (length - k)
for(let i = 1; i < k; i++){
pHead = pHead.next;
if (pHead == null) return null;
}
//traverse the linked list by (length - k) times, and we'll get the result
while (pHead.next){
node = node.next;
pHead = pHead.next;
}
return node;
} 2022/4/4
牛客网-剑指offer-知识分类篇-数据结构-链表jz18
7.删除链表的结点
-方法：找到待删结点的前一个结点，改变改结点指向。代码如下，
function deleteNode( head , val ) {
// corner case
if (!head) return null;
if (head.val === val) return head.next;
// find the element before the toBeDelete element
let res = head;
while (head !== null && head.next !== null && head.next.val !== val) head = head.next;
// delete the toBeDelete element
head.next = head.next.next;
return res;
} 
