鏈表中環(huán)的入口結(jié)點(diǎn)

題目：一個(gè)鏈表中包含環(huán)，如何找出環(huán)的入口結(jié)點(diǎn)？

解題思路

可以用兩個(gè)指針來解決這個(gè)問題。先定義兩個(gè)指針 P1 和 P2 指向鏈表的頭結(jié)點(diǎn)。如果鏈表中環(huán)有 n 個(gè)結(jié)點(diǎn)，指針 P1 在鏈表上向前移動(dòng) n 步，然后兩個(gè)指針以相同的速度向前移動(dòng)。當(dāng)?shù)诙€(gè)指針指向環(huán)的入口結(jié)點(diǎn)時(shí)，第一個(gè)指針已經(jīng)圍繞著環(huán)走了一圈又回到了入口結(jié)點(diǎn)。

剩下的問題就是如何得到環(huán)中結(jié)點(diǎn)的數(shù)目。我們?cè)诿嬖囶} 15 的第二個(gè)相關(guān)題目時(shí)用到了一快一慢的兩個(gè)指針。如果兩個(gè)指針相遇，表明鏈表中存在環(huán)。兩個(gè)指針相遇的結(jié)點(diǎn)一定是在環(huán)中?？梢詮倪@個(gè)結(jié)點(diǎn)出發(fā)，一邊繼續(xù)向前移動(dòng)一邊計(jì)數(shù)，當(dāng)再次回到這個(gè)結(jié)點(diǎn)時(shí)就可以得到環(huán)中結(jié)點(diǎn)數(shù)了。

結(jié)點(diǎn)定義

    private static class ListNode {
        private int val;
        private ListNode next;
        public ListNode() {
        }
        public ListNode(int val) {
            this.val = val;
        }
        @Override
        public String toString() {
            return val +"";
        }
    }

代碼實(shí)現(xiàn)

public class Test56 {
    private static class ListNode {
        private int val;
        private ListNode next;
        public ListNode() {
        }
        public ListNode(int val) {
            this.val = val;
        }
        @Override
        public String toString() {
            return val +"";
        }
    }
    public static ListNode meetingNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 鏈表中沒有環(huán)
        if (fast == null || fast.next == null) {
            return null;
        }
        // fast重新指向第一個(gè)結(jié)點(diǎn)
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    public static void main(String[] args) {
        test01();
        test02();
        test03();
    }
    // 1->2->3->4->5->6
    private static void test01() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        System.out.println(meetingNode(n1));
    }
    // 1->2->3->4->5->6
    //       ^        |
    //       |        |
    //       +--------+
    private static void test02() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n3;
        System.out.println(meetingNode(n1));
    }
    // 1->2->3->4->5->6 <-+
    //                |   |
    //                +---+
    private static void test03() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n6;
        System.out.println(meetingNode(n1));
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/74.png" alt="" />