尋找鏈表的入環節點和相交節點問題

作者：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 鏈表走兩步

然後 bigger 和 smaller 分別從 h2 和 h1 開始走，一定會在 x 相遇。如下圖

完整程式碼如下

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

演算法和數據結構筆記

Tags: leetcode 數據結構演算法演算法和數據結構鏈表