20230408

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

• 题目解读
  链表中找寻中间的节点，两种情况：1. 节点数为基数，那么取中间节点（共5个，取第3个）。2. 节点数为偶数，中间会有两个，取后面一个（共6个，取第4个）。

• 思路

1. 遍历列表，使用一个数组标记每个节点
2. 使用数组特性，寻找数组中间下标
3. 两种情况：奇数-> 5 / 2 = 2.5，我们实际会取第3个节点（即数组下标2）；偶数 -> 6 / 2 = 3，我们实际会取第4个节点（即数组下标3）
4. 不难看出，只需要对数组长度除2且向下取整

• AC样例

/* Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/* @param {ListNode} head* @return {ListNode}*/
var middleNode = function(head) {/* 遍历整个列表，通过一个数组记录每个位置* 找到数组的中间节点输出*/let arr = [];// 遍历并记录while (head) {arr.push(head);head = head.next;}let midIndex = Math.floor(arr.length / 2);return arr[midIndex];
};

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

• 题目解读
  链表中可能存在循环链表的情况，如果存在这样的情况，找到第一个循环开始的结点。如果不存在这样的情况，则返回null。

• 思路

1. 遍历链表，打标记
2. 遍历过程中，先判断是否被标记过，如果发现被标记过，那么当前结点就是循环开始的结点
3. 达标方式，1. 集合记录；2. 链表flag记录

• AC样例

/* Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//* @param {ListNode} head* @return {ListNode}*/
var detectCycle = function(head) {/* set集合记录已经遍历的节点* 当发现有遍历过的，则此节点为结果*/// let set = new Set();// let ans = null;// while (head) {//     if (set.has(head)) {//         ans = head;//         break;//     }//     set.add(head);//     head = head.next;// }// return ans;/* 在链表上记录一个flag，遍历过的节点标记为true* 当flag为true，则为结果*/let ans = null;while (head) {if (head.flag) {ans = head;break;}head.flag = true;head = head.next;}return ans;
};

声明
以上题目均来自于LeetCode，仅做学习使用
https://leetcode.cn/