1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：bit me 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】一套链表 OJ 带你轻松玩转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

meoj,数据结构,链表,数据结构,java

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


 

🏳️一. 移除链表元素

简介：

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

示例1：meoj,数据结构,链表,数据结构,java

输入：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的前驱

meoj,数据结构,链表,数据结构,java

每次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：
meoj,数据结构,链表,数据结构,java

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

示例 2：
meoj,数据结构,链表,数据结构,java

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

示例 3：

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

提示：

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

要求：

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

注意：

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

反转前的链表：
meoj,数据结构,链表,数据结构,java
反转后的链表：
meoj,数据结构,链表,数据结构,java
由上图可知，我们需要把头节点挪到最后面，让每个节点的指向发生反向改变，这时候我们就需要一个前驱信息来支撑我们的节点指向发生改变

  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为空，链表就反转完毕了

meoj,数据结构,链表,数据结构,java

注意：在我们第二步对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：
meoj,数据结构,链表,数据结构,java

输入：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 开始相交：meoj,数据结构,链表,数据结构,java

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

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

自定义评测：

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

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

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

示例 1：
meoj,数据结构,链表,数据结构,java

输入：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：meoj,数据结构,链表,数据结构,java

输入：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：
meoj,数据结构,链表,数据结构,java

输入：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：
meoj,数据结构,链表,数据结构,java

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

示例 2：
meoj,数据结构,链表,数据结构,java

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

示例 3：

meoj,数据结构,链表,数据结构,java

输入：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：

meoj,数据结构,链表,数据结构,java

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

示例 2：

meoj,数据结构,链表,数据结构,java

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

示例 3：

meoj,数据结构,链表,数据结构,java

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

提示：

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

导图：

meoj,数据结构,链表,数据结构,java

当两个引用相遇之后，因为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;
}

附上总的代码:文章来源地址https://www.toymoban.com/news/detail-815707.html

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;
}

到了这里，关于【数据结构与算法】一套链表 OJ 带你轻松玩转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】带你玩转排序：堆排序、希尔排序、插入排序、选择排序、冒泡排序、快排(多版本)、归并排序

    【数据结构】带你玩转排序：堆排序、希尔排序、插入排序、选择排序、冒泡排序、快排(多版本)、归并排序

    英杰社区 https://bbs.csdn.net/topics/617804998 目录 常见算法的实现         插入排序         希尔排序         堆排序         选择排序         冒泡排序         快速排序         Hoare版本         随机选Keyi               三数取中         挖坑法  

    2024年02月08日
    浏览(56)
  • 【数据结构与算法】手撕链表OJ题

    【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 思路一 ：一种比较普遍的方式，边遍历边找不同。我们可以通过定义两个指针，一个指向头节点，一个置为NULL。当遇到值为相同的时候，直接跳过去。指向下一位

    2024年02月10日
    浏览(45)
  • 【数据结构与算法】：10道链表经典OJ

    【数据结构与算法】：10道链表经典OJ

    思路1：遍历原链表，将 val 所在的节点释放掉。(太麻烦) 思路2：创建新链表，再遍历原链表，找到不为 val 的节点尾插到新链表。 思路1代码实现如下： 注意： 1.当链表为空时，直接返回NULL即可。 2.当尾插上最后一个有效节点时，此时它的 next 可能还与最后一个节点相链接，

    2024年04月14日
    浏览(39)
  • 【Java数据结构 -- 队列:队列有关面试oj算法题】

    【Java数据结构 -- 队列:队列有关面试oj算法题】

    只允许在一端进行插入数据操作，在另一端进行删除数据操作得特殊线性表，队列是 先进先出 ，入队：进行插入操作得一端称为 队尾（rear） ，出队：进行删除操作的一端称为 队头(front) 。队列Queue是个接口， 底层通过链表实现的 。 boolean offer(E e) – 入队列 E poll() – 出队

    2024年01月25日
    浏览(47)
  • 【数据结构与算法】一文带你学透——算法

    【数据结构与算法】一文带你学透——算法

       本期我们所要学习的内容是数据结构与算法中的算法的相关内容，通过上期我们学的数据结构想必大家都会了吧，在学习完毕之后算法，我想你已经可以编写出比较优秀的代码了， 著名计算机科学家沃思曾提出一个公式 程序=数据结构+算法。双剑合璧，天下无敌！   前言

    2024年02月07日
    浏览(39)
  • 手把手教你 ，带你彻底掌握八大排序算法【数据结构】

    手把手教你 ，带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法，其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 可以理解为一遍摸扑克牌，一边进行排序 在待排序的元素中，假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(66)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到，最大的公共子串长度为2，一共有两个长度为2的公共子串，分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符，即 ba 和 ac 根据上面的方法，我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(95)
  • 数据结构与算法——二叉树+带你实现表达式树（附源码）

    数据结构与算法——二叉树+带你实现表达式树（附源码）

    📖作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋阶段， 因为最近参加新星计划算法赛道(白佬)，所以加快了脚步，果然急迫感会增加动力 ——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的 📖作者主页：king南星 📖

    2024年01月25日
    浏览(50)
  • 【数据结构与算法】：带你手搓顺序表（C/C++篇）

    【数据结构与算法】：带你手搓顺序表（C/C++篇）

    一、顺序表 1.1 线性表 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连

    2024年04月28日
    浏览(33)
  • 数据结构与算法之美学习笔记：41 | 动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

    数据结构与算法之美学习笔记：41 | 动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

    本节课程思维导图： 今天，我主要讲动态规划的一些理论知识。学完这节内容，可以帮你解决这样几个问题：什么样的问题可以用动态规划解决？解决动态规划问题的一般思考过程是什么样的？贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？ 什么样的问

    2024年02月02日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包