环形链表问题 | YOLOのBLOG

一、链表的中间结点（简）

题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：
给定链表的结点数介于 1 和 100 之间。

题解

利用快慢指针，快指针一次走两步，慢指针一次走一步。当快指针走到尽头时，此时慢指针对应的九三中间结点。

class Solution {
 public:
  ListNode* middleNode(ListNode* head) {
    if (!head) {
      return NULL;
    }
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
    }
    return slow;
  }
};

二、环形链表（简）

题目

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

示例 1：

graph LR
  3 --> 2 --> 0 --> -4
  -4 --> 2

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

flowchart LR
  1 --> 2
  2 --> 1

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

flowchart LR
  1

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个有效索引。

题解

利用快慢指针，快指针一次走两步，慢指针一次走一步。因为快指针快，慢指针慢，所以如果有环快指针最后一定会追上慢指针

class Solution {
 public:
  bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
      return false;
    }
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast->next && fast->next->next) {
      if(!slow->next) {
        return false;		// 稍微加个判断，减少下用时
      }
      slow = slow->next;
      fast = fast->next->next;
      if (fast == slow) {
        return true;
      }
    }
    return false;
  }
};

// 另一种表示方法是
ListNode *slow = head;
ListNode *fast = head->next;
// 两种方式不同点在于,一般用fast=head->next较多,因为这样可以知道相交点的上一个节点,可以用来删除等操作
// fast如果初始化为head->next,则相交点在slow->next
// fast初始化为head,则相交点在slow

三、环形链表 II（中）

题目

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

示例 1：

flowchart LR
  3 --> 2 --> 0 --> -4
  -4 --> 2

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

flowchart LR
  1 --> 2
  2 --> 1

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

flowchart LR
  1

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：
链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

题解

这道题是要求入环点，首先要判断有环，这个就直接照搬上一题。主要是怎么找入环点。可以看下面这张图

F为第一个节点-F到入环点0的距离；
a为入环点0到相遇点h距离；
b为相遇点h到入环点0距离；
当fast和slow相遇时，因为fast每次走两步，slow每次一步，所以fast走过的是slow的两倍，设slow走过为S，则S=F+a，2S=F+a+b+a，故F=b；
现在让slow返回第一个节点，fast处于第一次相遇的节点，此时slow从第一个节点出发，因为F=b，所以fast和slow会在入环口第二次相遇，即为所求节点。

class Solution {
 public:
  ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) {
      return NULL;
    }
    bool hasCycle = false;
    // 先判断是否有环
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
      if (!slow->next) {
        break;
      }
      slow = slow->next;
      fast = fast->next->next;
      if (fast == slow) {
        hasCycle = true;
        break;
      }
    }
    // 有环则找入环开始的节点
    if (hasCycle) {
      slow = head;
      while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
      }
      return slow;
    }
    return NULL;
  }
};