寻找链表的入环节点和相交节点问题

寻找链表的入环节点和相交节点问题

作者:Grey

原文地址:

博客园:寻找链表的入环节点和相交节点问题

CSDN:寻找链表的入环节点和相交节点问题

判断链表中是否有环

给你一个链表的头节点 head ,判断链表中是否有环。

题目链接见:LeetCode 141. Linked List Cycle

主要思路

使用快慢指针,从链表头开始,快指针(fast)一次走两步,慢指针(slow)一次走一步,如果快指针会走到 null,则说明无环;否则有环,而且有环情况下,快慢指针必在某个位置相遇,即:slow == fast

完整代码如下

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

链表开始入环的第一个节点

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

题目链接见:LeetCode 142. Linked List Cycle II

主要思路

使用快慢指针,从链表头开始,快指针一次走两步,慢指针一次走一步,如果快指针会走到 null,则说明无环;

如果有环,则快指针和慢指针必在某个节点相遇,假设在 m 节点相遇,然后快指针回到链表头节点,慢指针停留在 m,

接下来继续:

快指针一次走两步;慢指针一次走一步。

快慢指针再次相遇的点就是第一个入环节点。

完整代码如下

public class Solution {
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        // 1. 快指针一次走两步,慢指针一次走一步
        // 2. 如果无环,快指针一定会走到空
        // 3. 如果有环,快指针和慢指针一定会在某处相遇。
        // 4. 相遇后,快指针回到原点,慢指针保持在原地
        // 5. 快慢指针同时每次走一步,一定在入环处相遇
        ListNode fast = head;
        ListNode 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;
        }
        // 快指针回到头节点
        // 慢指针停留在原处
        if (fast == slow) {
            fast = head;
        }
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

两个链表相交的起始节点

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

注:本题中保证整个链式结构中不存在环。

题目链接:LeetCode 160. Intersection of Two Linked Lists

主要思路:

如果两个链表是相交的,则两个链表的最后一个节点一定是一样的,如果两个链表最后一个节点不一样,则一定不相交。

先获取两个链表的长度,将其中长度更长的链表设置为 bigger,长度为 len1;更短的链表设置为 smaller,长度为 len2。

两个链表长度的差值 gap = len1 - len2,接下来,分别设置两个指针指向 bigger 链表头部和 smaller 链表的头部,

先让 bigger 链表的头部指针走gap步,然后 bigger 指针开始和 smaller 指针同步走,如果两个链表相交,则一定在相交的起始节点相遇,如果不相交,则两个链表会走向 null 节点(由于题目已经确保了链式结构中不存在环)。

如下示例图,其中 smaller 和 bigger 链表如下,x 节点是相交节点

寻找链表的入环节点和相交节点问题插图

先让 bigger 链表走两步

寻找链表的入环节点和相交节点问题插图1

然后 bigger 和 smaller 分别从 h2 和 h1 开始走,一定会在 x 相遇。如下图

寻找链表的入环节点和相交节点问题插图2

完整代码如下

public class Solution {
  public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (null == headA || null == headB) {
            return null;
        }
        if (headA.next == null && headB.next == null) {
            return headA == headB ? headA : null;
        }
        int lenOfA = getLen(headA);
        int lenOfB = getLen(headB);
        ListNode bigger = lenOfA > lenOfB ? headA : headB;
        ListNode smaller = bigger == headA ? headB : headA;
        int gap = Math.abs(lenOfA - lenOfB);
        while (gap != 0) {
            bigger = bigger.next;
            gap--;
        }
        while (bigger != null && smaller != null) {
            if (bigger == smaller) {
                return bigger;
            }
            bigger = bigger.next;
            smaller = smaller.next;
        }
        return null;
    }

    public static int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}

更多

算法和数据结构笔记

文章来源于互联网:寻找链表的入环节点和相交节点问题

THE END
分享
二维码