链表算法 篇三

发布时间:2023-05-15 09:31:22

单链表的中点

package com.2023年,algorithm.linkedlist;/** * https://leetcode.cn/problems/middle-of-the-linked-list/submissions/432318762/ * 单链表的中点 * 问题的关键是我们不能直接得到单链表的长度 n,常规方法也是第一次计算历链表 n,再一次得到第一次 n / 2 一个节点,即中间节点。 * * 如果你想得到一个中间节点,你也需要玩一些聪明,使用它「快慢指针」的技巧: * * 让我们给两个指针 slow 和 fast 分别指向链表头结点 head。 * * 如果你想得到一个中间节点,你也需要玩一些聪明,使用它「快慢指针」的技巧: * * 让我们给两个指针 slow 和 fast 分别指向链表头结点 head。 * * 每当慢指针 slow 进一步,快指针 fast 前进两步,这样,当 fast 走到链表末尾,slow 指向链表中点。 */public class Demo5 {    public static class ListNode {        int val;        ListNode next;        ListNode() {        }        ListNode(int val) {            this.val = val;        }        ListNode(int val, ListNode next) {            this.val = val;            this.next = next;        }    }    ListNode middleNode(ListNode head){        ///慢慢指向head        ListNode slow = head,fast = head;        while (slow != null && fast.next != null && fast.next != null){            slow = slow.next;            fast = fast.next.next;        }        return slow;    }}
链表是否成环+环的起点?

每当慢指针 slow 进一步,快指针 fast 两步前进。

如果 fast 最后遇到空指针,说明链表没有环;如果 fast 最终和 slow 相遇,那一定是 fast 超过了 slow 一圈,说明链表中含有环。

只需稍加修改搜索链表中点的代码即可:

package com.2023年,algorithm.linkedlist;/** * 1 判断链表是否成环(环形链表) * https://leetcode.cn/problems/linked-list-cycle/ * 2 环的起点(环形链表Ⅱ) * https://leetcode.cn/problems/linked-list-cycle-ii/ * 判断链表是否包含环是一个经典问题,快慢指针也用于解决方案: *  */public class Demo6 {    class ListNode {        int val;        ListNode next;    }    boolean hasCycle(ListNode head) {        ListNode slow = head, fast = head;        while (slow != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            ///fast是slow的两倍速存在环,应该有相等的节点            if (fast == slow) {                return true;            }        }        return false;    }    ///环的起点    public ListNode detectCycle(ListNode head) {        ListNode fast, slow;        fast = slow = head;        while (fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;            if (fast == slow) break;        }        if(fast == null || fast.next == null){            return null;        }        ///慢指针重新指向头节点        slow = head;        ///快指针比慢指针多走K步,设置起点距离相遇点为m步,k-m为环起点        while (slow != fast){            fast = fast.next;            slow = slow.next;        }        return slow;    }}

当我们假设慢指针相遇时,我们假设慢指针 slow 走了 k 步骤,指针这么快 fast 一定走了 2k 步:

链表算法 篇三_链表

fast 一定比 slow 多走了 k 步骤,这多走 k 步其实就是 fast 指针在环中转圈,所以 k 值为环长「整数倍」。

假设相遇点距环的起点距离为 m,然后结合上图 slow 指针,环的起点距离头结点 head 的距离为 k - m,也就是说,如果从 head 前进 k - m 步骤可以到达环起点。

巧合的是,如果你继续从相遇点前进 k - m 步骤,也正好到达环的起点。因为结合上图 fast 指针,从相遇点走k步可以转回相遇点 k - m 步骤必须走到环的起点:

链表算法 篇三_头结点_02

因此,只要我们重新指向快慢指针中的任何一个 head,然后两个指针同速前进,k - m 步后一定会相遇,相遇的地方就是环的起点。

环的相遇点和环的起点

假设我们有一个链表:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3.节点3后面的部分形成一个环。

首先,我们使用快速和缓慢的指针算法来判断链表是否有一个环。我们每次设置两步快速指针,每步慢速指针,并从链表的起点开始。当快速指针赶上慢速指针时,表示链表中有一个环。在这种情况下,快速指针和慢速指针在6个节点相遇。

接下来,我们需要区分环的起点。为此,我们再次使用快指针算法,但这次我们让快指针从相遇点开始,让慢指针回到起点。然后,快指针每次走两步,慢指针每次走一步,直到他们再次相遇。所以他们相遇的节点是环的起点。

在这种情况下,我们让慢指针回到起点1,让快指针从相遇点6开始。第一步快速指针可以到达节点3,第二步到达节点4,第三步到达节点5,第四步回到节点3。在这个过程中,慢指针只走了一步,到达了节点2。然后,我们让快指针回到起点6,速度变成每次一步,慢指针继续每次一步。当他们再次相遇时,他们遇到的节点是环的起点,即节点3。

因此,在这个例子中,相遇点是节点6,而环的起点是节点3。

链表是否相交

链表算法 篇三_链表_03

若使用两个指针 p1p2 在两个链表上分别前进,不能同时进入公共节点,也不能得到交叉节点 c1

解决这个问题的关键是通过某种方式让它走 p1p2 可同时到达相交节点 c1

所以,我们可以放手 p1 遍历完链表 A 之后开始遍历链表 B,让 p2 遍历完链表 B 之后开始遍历链表 A,这样相当于「逻辑上」两个链表连接在一起。

如果这样拼接,就可以了 p1p2 同时进入公共部分,即同时到达相交节点 c1

链表算法 篇三_链表_04

package com.2023年,algorithm.linkedlist;/** * 两个链表是否相交(相交链表) * https://leetcode.cn/problems/intersection-of-two-linked-lists/ */public class Demo7 { class ListNode { int val; ListNode next; } ListNode getIntersectionNode(ListNode headA, ListNode headB) { // p1 指向 A 链表头结点,p2 指向 B 链表头结点 ListNode p1 = headA, p2 = headB; while (p1 != p2) { // p1 走一步,如果你走 A 链表末尾,转到 B 链表 if (p1 == null) p1 = headB; else p1 = p1.next; // p2 走一步,如果走到 B 链表末尾,转到 A 链表 if (p2 == null) p2 = headA; else p2 = p2.next; } return p1; }}

上一篇 Java电影订票管理系统
下一篇 深入MVC模式和三层架构

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题