当前位置： 首页 > news >正文

【数据结构与算法】一套链表 OJ 带你轻松玩转链表

news 来源：原创 2024/4/28 11:59:38

请添加图片描述

✨个人主页：bit me
✨当前专栏：数据结构
✨刷题专栏：基础算法

链 表 OJ

  • 🏳️一. 移除链表元素
  • 🏴二.反转链表
  • 🏁三.链表的中间结点
  • 🚩四.链表中倒数第k个结点
  • 🏳️‍🌈五.合并两个有序链表
  • 🏳️‍⚧️六.链表的回文结构
  • 🏴‍☠️七.链表分割
  • 🏴󠁧󠁢󠁷󠁬󠁳󠁿八.相交链表
  • 🏳️‍🌈九.环形链表
  • 🍹十.环形链表 II

 

🏳️一. 移除链表元素

简介：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1：请添加图片描述

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例2：

输入：head = [], val = 1
输出：[]

示例3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

①：列表中的节点数目在范围 [0, 104] 内
②：1 <= Node.val <= 50
③：0 <= val <= 50

要求：

①：时间复杂度O(n)
②：只遍历单链表一次

首先我们需要知道的是：

删除的核心是 需要找到这个节点的前一个节点是谁

所以我们在这里定两个指针cur和prev，其中cur代表的是要删除的节点，prev代表的是cur的前驱

在这里插入图片描述

每次cur走一步的时候，prev都会紧随其后，当cur遇到了要删除的链表，都会直接往后走，直到遇到非val值的节点，然后prev继续跟着cur走

  1. 先考虑特殊情况：头节点不为空
if(head == null){
    return null;
}
  1. 定义cur和prev指针位置
ListNode cur = head.next;
ListNode prev = head;
  1. 在删除节点之前，我们得知道cur走动的前提是不为空的
while(cur != null){
	......
}
  1. 在cur 不为空的前提下，我们该如何删除元素呢？

如第二个节点为我们要删除的元素，直接让prev(head)指向第三个元素的下标，第三个元素的下标就是cur.next，所以最终的式子就是prev.next = cur.next，然后让cur继续往后面走，继续执行此代码

if(cur.val == val){
    prev.next = cur.next;
    cur = cur.next;
}else{
    prev = cur;
    cur = cur.next;
}
  1. 最终代码就完成了，但是还有一个特殊情况，那就是cur是从第二个元素开始遍历，并没有考虑到头节点，所以我们在这里单独判断一下头节点
if(head.val == val){
    head = head.next;
}

附上总的代码：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }

        ListNode cur = head.next;
        ListNode prev = head;

        while(cur != null){
            if(cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }

        //单独处理了头节点
        if(head.val == val){
            head = head.next;
        }
        
        return head;
    }
}

 

🏴二.反转链表

简介：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
请添加图片描述

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
请添加图片描述

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

①：链表中节点的数目范围是 [0, 5000]
②：-5000 <= Node.val <= 5000

要求：

时间复杂度：O(n)
空间复杂度：O(1)

注意：

此处的反转链表可不是逆序输出就可以的，如下图所示

反转前的链表：
在这里插入图片描述
反转后的链表：
在这里插入图片描述
由上图可知，我们需要把头节点挪到最后面，让每个节点的指向发生反向改变，这时候我们就需要一个前驱信息来支撑我们的节点指向发生改变

  1. 先考虑特殊情况

①：当头节点为空的情况下直接返回空

if(head == null){
    return null;
}

②：只有一个节点

if(head.next == null){
    return head;
}
  1. 根据图表直接把头节点的next设为null
head.next = null;
  1. 定义两个指针，一个遍历转变节点指向的指针cur，一个成为前驱信息支撑第一个指针遍历的指针curNext，cur在头节点head后一位

前驱信息指针curNext始终在cur后一位，我们进行链表反转，把cur的next指向头节点head，再让head挪到cur的位置，cur继续往后走走到curNext的位置，如此循环直到cur为空，链表就反转完毕了

在这里插入图片描述

注意：在我们第二步对head头节点进行置为null之前，我们就需要先把cur定义好，否则cur是为空的

ListNode cur = head.next;

反转循环：

while(cur != null){
    ListNode curNext = cur.next;
    cur.next = head;
    head = cur;
    cur = curNext;
}

总结：其实链表的反转相当于链表头插法，我们把头节点后的节点依次插入到头节点之前，就完成了链表的反转

附上总的代码:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        //只有一个头节点
        if(head.next == null){
            return head;
        }

        ListNode cur = head.next;
        head.next = null;
       
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

 

🏁三.链表的中间结点

简介：

给定一个头结点为 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 之间。

要求：

时间复杂度为：O(n)
只能遍历单链表一遍

思路：

  1. 对于求链表中间节点，最简单的想法就是链表遍历一次除2，但是按照我们上面要求来，是绝对不行的，有更好的解法是必要的
  2. 我们只需要定义快慢指针就可以完成我们的需求，快指针是慢指针的两倍速度
  3. 当节点数为奇数的时候，快慢指针一起走，当快指针fast.next == null的时候，慢指针slow为中间节点
  4. 当节点数为偶数的时候，快慢指针一起走，当快指针fast == null的时候，慢指针slow为中间节点
     
    原理就是当路程一定的时候，速度如果是二倍，当快的走到最后的时候，慢的一定在路程中间位置

定义快慢指针，判断终止条件及快慢指针的走动

public ListNode middleNode(){
	ListNode fast = head;
	ListNode slow = head;
	while(fast != null && fast.next != null){
   		fast = fast.next.next;
    	slow = slow.next;
	}
	return slow;
}

判断条件顺序不可调动 不然可能发生空指针异常
fast为空的话，fast.next就发生空指针异常了

 

🚩四.链表中倒数第k个结点

描述：

输入一个链表，输出该链表中倒数第k个结点。

示例1:

输入：1,{1,2,3,4,5}
返回值：{5}

思路：

  1. 此出照样使用快慢指针
  2. 找出这里快慢指针的规律及判断条件
  3. 例如我们要找的 k = 4 ，总的节点数为5个，这时候就可以让快指针先走，慢指针后走，慢指针所指向的位置就是k，所以当慢指针走到2，快指针走到了5，快指针就达到了临界条件停止了，返回了慢指针的位置，此时快指针比慢指针快3步，以此类推，快指针比慢指针快 k - 1 步的时候，当快指针遇到空，此时慢指针所指的位置就是第k个节点
  1. 先考虑特殊情况（k的合法性和头节点）
if(k <= 0 ){
    return null;
}
if(head == null){
    return null;
}

此处没有判断k会不会大于size()是因为在后面代码中k已经判断了，执行了走的步数，要是大于size()就会溢出步数从而发生错误，所以此处就可以不用判断

  1. 定义快慢指针，并且执行快指针比慢指针多的步数
ListNode fast = head;
ListNode slow = head;
while(k - 1 > 0){
    fast = fast.next;
    if(fast == null){
        return null;
    }
    k--;
}
  1. 当快指针比慢指针快了 k - 1 步的时候，两个指针一起走，直至快指针达到临界条件
while (fast.next != null){
    fast = fast.next;
    slow = slow.next;
}

附上总的代码:

public ListNode findKthTOTail(int k){
    if(k <= 0 ){
        return null;
    }
    if(head == null){
        return null;
    }

    ListNode fast = head;
    ListNode slow = head;

    while(k - 1 > 0){
        fast = fast.next;
        if(fast == null){
            return null;
        }
        k--;
    }
    //fast已经走了k-1步了
    while (fast.next != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

 

🏳️‍🌈五.合并两个有序链表

要求：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
请添加图片描述

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  1. 两个链表的节点数目范围是 [0, 50]
  2. -100 <= Node.val <= 100
  3. l1 和 l2 均按 非递减顺序 排列

思路：

定义两个链表的头节点，然后一起遍历两个链表，依次遍历的时候比较俩链表单个节点大小，小的节点就放在前面，大的节点就放在后面，然后排序就完成了

  1. 先考虑特殊情况，任何一链表为空
if (head1 == null) return head2;
if (head2 == null) return head1;
  1. 定义一个新的链表来接收俩链表的合成，并且定义一个新的指针完成比较大小的走动来遍历打印新的链表
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;

此处给定了参数 -1 在这里无意义，只是题目要求带参，所以随机给一个

  1. tmp作为新的指针，在比较俩链表遍历大小时，每当俩节点谁最小，tmp便指向它，然后一直这样走，就可以把俩链表整体大小归纳到tmp当中，传输给newHead链表
while(head1 != null && head2 != null){
    if(head1.val < head2.val){
        tmp.next = head1;
        tmp = tmp.next;
        head1 = head1.next;
    }else {
        tmp.next = head2;
        tmp = tmp.next;
        head2 = head2.next;
    }
}
  1. 在这里我们还有个特殊情况，当任意一个链表走完之后，我们另外的一个链表就不用比较了，直接把剩下的节点拼接上去就可以
if(head1 != null){
    tmp.next = head1;
}
if(head2 != null){
    tmp.next = head2;
}

附上总的代码:

public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
    if (head1 == null) return head2;
    if (head2 == null) return head1;

    ListNode newHead = new ListNode(-1);
    ListNode tmp = newHead;

    while(head1 != null && head2 != null){
        if(head1.val < head2.val){
            tmp.next = head1;
            tmp = tmp.next;
            head1 = head1.next;
        }else {
            tmp.next = head2;
            tmp = tmp.next;
            head2 = head2.next;
        }
    }
    if(head1 != null){
        tmp.next = head1;
    }
    if(head2 != null){
        tmp.next = head2;
    }
    return newHead.next;
}

 

🏳️‍⚧️六.链表的回文结构

描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

思路：

对于回文，我们需要找到中间节点，然后把后半部分反转，从最后面开始遍历到中间和从开头遍历到中间值是一样的，说明就是回文串

  1. 考虑特殊情况，链表为空或者只有一个头节点
if(this.head == null) return false;
if (this.head.next == null) return true;//只有一个节点
  1. 找中间节点
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
}
  1. 反转后半部分链表
ListNode cur = slow.next;
while(cur != null){
    ListNode curNext = cur.next;
    cur.next = slow;
    slow = cur;
    cur = curNext;
}
  1. slow走到最后一个节点的时候，往中间遍历，此时头节点往中间遍历，看两边分别遍历是否相同，判断是否为回文串
while (head != slow){
    if(head.val != slow.val){
        return false;
    }
    //偶数的情况
    if (head.next == slow){
        return true;
    }
    head = head.next;
    slow = slow.next;
}
  1. 奇数个节点情况下，当head和slow的值域不相等的情况下就不是回文
  2. 偶数的情况下，当遍历到相邻的时候，，判断是否是相引用即可

附上总的代码:

public boolean chkPalindrome() {
    if(this.head == null) return false;
    if (this.head.next == null) return true;//只有一个节点

    //1.找中间节点
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    //2.slow一定是中间节点,再翻转
    ListNode cur = slow.next;
    while(cur != null){
        ListNode curNext = cur.next;
        cur.next = slow;
        slow = cur;
        cur = curNext;
    }
    //3.slow走到了最后一个节点的地方
    while (head != slow){
        if(head.val != slow.val){
            return false;
        }
        //偶数的情况
        if (head.next == slow){
            return true;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
}

 

🏴‍☠️七.链表分割

描述：

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

注意：

x的值也可以是链表中没有的值

思路：

我们创建两个链表，一条链表存储小于x的节点，一条链表存储大于x的节点，最终合并两条链表所得的一条完整的链表就是我们要的链表分割结果

  1. 考虑特殊情况
if(head == null) return null;
  1. 定义两条链表的首尾节点
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
  1. 遍历链表，然后进行分类，判断是分类到哪一条新链表中（尾插）
ListNode cur = head;
while(cur != null){
    if(cur.val < x){
        //判断是不是第一次插入
        if(bs == null){
            bs = cur;
            be = cur;
        }else {
            be.next = cur;
            be = be.next;
        }
    }else {
        if(as == null){
            as = cur;
            ae = cur;
        }else {
            ae.next = cur;
            ae = ae.next;
        }
    }
    cur = cur.next;
}
  1. 判断元素大小然后进行分类，小于x的节点放在 bs – be 这条链表上，大于x的节点放在 as – ae 这条链表上
  2. 每个链表第一次插入是特殊情况，要特殊处理
  3. 除了第一个元素之外，我们再进行尾插的时候让 be，ae 走动，因为它俩是尾节点
  1. 拼接两个新链表
if(bs == null){
    //说明第一个区间没有数据
    return as;
}
be.next = as;
if(as != null){
    ae.next = null;
}
return bs;

注意特殊情况：第一个新链表可能没数据，然后记得把第二个尾节点置为空结束

附上总的代码:

public ListNode partition(int x) {
    if(head == null) return null;
    ListNode bs = null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;

    ListNode cur = head;
    while(cur != null){
        if(cur.val < x){
            //判断是不是第一次插入
            if(bs == null){
                bs = cur;
                be = cur;
            }else {
                be.next = cur;
                be = be.next;
            }
        }else {
            if(as == null){
                as = cur;
                ae = cur;
            }else {
                ae.next = cur;
                ae = ae.next;
            }
        }
        cur = cur.next;
    }
    if(bs == null){
        //说明第一个区间没有数据
        return as;
    }
    be.next = as;
    if(as != null){
        ae.next = null;
    }
    return bs;
}

 

🏴󠁧󠁢󠁷󠁬󠁳󠁿八.相交链表

简介：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：请添加图片描述

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  1. intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  2. listA - 第一个链表
  3. listB - 第二个链表
  4. skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  5. skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：
请添加图片描述

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
 
输出：Intersected at ‘8’
 
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：请添加图片描述

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 
输出：Intersected at ‘2’
 
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：
请添加图片描述

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 
输出：null
 
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  1. listA 中节点数目为 m
  2. listB 中节点数目为 n
  3. 1 <= m, n <= 3 * 10^4
  4. 1 <= Node.val <= 10^5
  5. 0 <= skipA <= m
  6. 0 <= skipB <= n
  7. 如果 listA 和 listB 没有交点，intersectVal 为 0
  8. 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

要求：

空间复杂度O(1)
时间复杂度O(m+n)

思路：

  1. 求两个链表的长度
  2. 让长的链表先走差值步
  3. 然后两个链表一起走，直到相遇
  1. 特殊情况，有链表为空
if(headA == null || headB == null) return null;
  1. 遍历两个链表的长度
int lenA = 0;
int lenB = 0;
ListNode pl = headA;//pl：永远指向长的链表
ListNode ps = headB;//ps：永远指向短的链表

while(pl != null){
    lenA++;
    pl = pl.next;
}

while (ps != null){
    lenB++;
    ps = ps.next;
}

在这里我们的lenA永远指向长的链表，我们接着往下看

  1. 我们还需要用到pl，ps，所以这里还需要换回来
pl = headA;
ps = headB;
  1. 差值步的计算和判断
//差值步 计算
int len = lenA - lenB;
if(len < 0){
    pl = headB;
    ps = headA;
    len = lenB - lenA;//更新差值步
}
//走到这里，pl一定指向的是那个最长的链表，ps一定指向的是最短的链表，且len一定是一个正数

while (len != 0){
    pl = pl.next;
    len--;
}
//说明pl走了差值步了，接下来一起走直到他们两个相遇

这里面我们把长的链表指向pl，保证了差值步为正数，然后让长链表先走差值步

  1. 差值步走完，俩链表一起走，直到相遇
while(pl != ps){
    pl = pl.next;
    ps = ps.next;
}
  1. 还要考虑特殊情况，没有交点的时候
if(headA == headB && headA == null){
    return null;
}

附上总的代码:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null) return null;

    //1，求俩个链表的长度
    int lenA = 0;
    int lenB = 0;
    ListNode pl = headA;//pl：永远指向长的链表
    ListNode ps = headB;//ps：永远指向短的链表

    while(pl != null){
        lenA++;
        pl = pl.next;
    }

    while (ps != null){
        lenB++;
        ps = ps.next;
    }

    pl = headA;
    ps = headB;
    //差值步 计算
    int len = lenA - lenB;
    if(len < 0){
        pl = headB;
        ps = headA;
        len = lenB - lenA;//更新差值步
    }
    //走到这里，pl一定指向的是那个最长的链表，ps一定指向的是最短的链表，且len一定是一个正数

    while (len != 0){
        pl = pl.next;
        len--;
    }
    //说明pl走了差值步了，接下来一起走直到他们两个相遇
    while(pl != ps){
        pl = pl.next;
        ps = ps.next;
    }

    //说明没有交点
    if(headA == headB && headA == null){
        return null;
    }
    return pl;
}

 

🏳️‍🌈九.环形链表

简介：

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

示例 1：
请添加图片描述

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

示例 2：
请添加图片描述

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

示例 3：

请添加图片描述

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

提示：

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

思路：

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

扩展问题：

  1. 为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇

  1. 快指针一次走3步，走4步，…n步行吗？

不可以，比如当环形长度为2，快慢指针一起走，快指针起点比慢指针多一步，慢指针每次走一步，快指针每次走三步，那他们永远都不会相遇

附上总的代码:

public boolean hasCycle(ListNode head) {
    if(head == null) return false;
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}

 

🍹十.环形链表 II

简介：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

示例 1：

请添加图片描述

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

示例 2：

请添加图片描述

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

示例 3：

请添加图片描述

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

提示：

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

导图：

在这里插入图片描述

当两个引用相遇之后，因为fast的速度是slow的速度的两倍，所以，此时fast的路程是slow的两倍

思路：

  1. 起始点到入口点的距离为X
  2. 环的长度设置为C
  3. 设相遇点到入口的距离为Y

fast只走了一圈的情况下：

slow走的路程：X + C - Y
 
fast走的路程：X + C + C - Y
 
按照路程倍数关系列等式：2*(X + C - Y) = X + C + C - Y
化简可得：X = Y

fast走了n圈：

slow走的路程：X + C - Y
 
fast走的路程：X + NC + C - Y
 
按照路程倍数关系列等式：2*(X + C - Y) = X + NC + C - Y
化简可得：X = (N - 1)*C + Y

总结：此处说明fast此时如果和slow速度一样，让slow从起点开始走，再走X步他们就会在相遇点相遇

  1. 考虑特殊情况
if(head == null) return null;
  1. 定义快慢指针，并且由总结可知，相遇的时候需要另外挪动指针
ListNode fast = head;
ListNode slow = head;

while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
    if(fast == slow){
        break;
    }
}
  1. break之后有两种情况，一是不满足循环，二是遇到break;说明是环且相遇
if(fast == null || fast.next == null){
    return null;
}
slow = head;
while(slow != fast){
    fast = fast.next;
    slow = slow.next;
}

附上总的代码:

public ListNode detectCycle(ListNode head) {
    if(head == null) return null;
    ListNode fast = head;
    ListNode slow = head;

    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            break;
        }
    }
    //走到这里说明遇到俩种情况
    //1.不满足循环，有一个为空
    //2.遇到break;说明是环且相遇
    if(fast == null || fast.next == null){
        return null;
    }
    slow = head;
    while(slow != fast){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

相关文章：

  • C/C++大学课程信息系统
  • 【网络编程】第三章 网络套接字（TCP协议程序+多进程+多线程+线程池）
  • 基于物联网设计的自反馈深紫外杀菌消毒系统(STM32F407)
  • react路由v6版本NavLink的两个小坑及解决
  • CSDN第11期周赛总结
  • 编程语言介绍
  • 【火灾检测】森林火灾检测系统（带面板）【含GUI Matlab源码 1921期】
  • Tomcat经验2
  • 为什么说C++太复杂（复杂到哪了？）
  • k8s部署手册-v03
  • 基于keras与tensorflow手工实现ResNet50网络
  • c语言中常用的字符串处理函数总结
  • ESP-01S使用AT指令连接阿里云
  • 第十四届蓝桥杯模拟赛第二期部分题答案（C++代码）
  • 面试半年，上个月成功拿到阿里offer，全靠我啃烂了学长给的这份笔记
  • ［分享］iOS开发－关于在xcode中引用文件夹右边出现问号的解决办法
  • 《微软的软件测试之道》成书始末、出版宣告、补充致谢名单及相关信息
  • 【刷算法】从上往下打印二叉树
  • Angular 4.x 动态创建组件
  • AWS实战 - 利用IAM对S3做访问控制
  • gf框架之分页模块(五) - 自定义分页
  • javascript 总结（常用工具类的封装）
  • LeetCode刷题——29. Divide Two Integers（Part 1靠自己）
  • react-native 安卓真机环境搭建
  • 产品三维模型在线预览
  • 机器人定位导航技术 激光SLAM与视觉SLAM谁更胜一筹？
  • 使用common-codec进行md5加密
  • 新版博客前端前瞻
  •  一套莫尔斯电报听写、翻译系统
  • 中国人寿如何基于容器搭建金融PaaS云平台
  • 好程序员大数据教程Hadoop全分布安装（非HA)
  • #!/usr/bin/python与#!/usr/bin/env python的区别
  • （26）4.7 字符函数和字符串函数
  • **python多态
  • ./configure,make,make install的作用(转)
  • .NET 4 并行（多核）“.NET研究”编程系列之二 从Task开始
  • .NET Core 版本不支持的问题
  • .NET Core 实现 Redis 批量查询指定格式的Key
  • [ NOI 2001 ] 食物链
  • [2016.7 test.5] T1
  • [CSS]盒子模型
  • [Mac软件]Adobe XD(Experience Design) v57.1.12.2一个功能强大的原型设计软件
  • [OGRE]看备注学编程(02)：打地鼠01-布置场地九只地鼠
  • [Oh My C++ Diary]\t \n \r的用法
  • [one_demo_10]递归解决汉诺塔问题
  • [paper] lift,splat,shooting 论文浅析
  • [poj3686]The Windy's(费用流)
  • [SpringBoot] AOP-AspectJ 切面技术
  • [Vue]路由传参 命名路由
  • [Windows 编程] Windows 7 开发教程，Windows 7 SDK 下载
  • [Windows]修改默认远程端口3389
  • [翻译] RSKImageCropper
  • [技术评论]龙芯电脑
  • [密码学]Base64编码
  • [深度学习]yolov9+deepsort+pyqt5实现目标追踪