环形链表 II

刘勋 · 刘勋 · commit 1605b8f3e74f · 2020-05-19T21:06:57.000+08:00
diff --git a/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution6.java b/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution6.java
@@ -0,0 +1,49 @@
+package com.algorithm.study.demo.algorithm.leetcode;
+
+/**
+ * @author xun2.liu
+ * @title: Solution6
+ * @projectName algorithm-study
+ * @description: 编写一个程序，找到两个单链表相交的起始节点。
+ * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
+ * 输出：Reference of the node with value = 8
+ *
+ * 来源：力扣（LeetCode）
+ * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
+ * @date 2020/5/18 19:35
+ */
+public class Solution6 {
+    public static class ListNode {
+        int val;
+        ListNode next;
+        ListNode(int x) { val = x; }
+    }
+    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
+        //使用两个指针分别指向headA、headB
+        //同时遍历两个连表
+        //当headA遍历完后指针指向headB，当headB遍历完后指针指向headA
+        //如此循环当两个指正都为Null的话代表没有相交的节点。
+        //如果都两个指针对应的节点相等就返回相等的节点就是相交的节点
+        ListNode p1=headA;
+        ListNode p2=headB;
+        while(p1!=p2){
+            p1=p1==null?headB:p1.next;
+            p2=p2==null?headA:p2.next;
+        }
+        return p1;
+    }
+
+    public static void main(String[] args) {
+        ListNode a=new ListNode(5);
+        ListNode b=new ListNode(4);
+        a.next=b;
+        ListNode c=new ListNode(6);
+        ListNode intersectionNode = getIntersectionNode(a, b);
+        if (null!=intersectionNode){
+            System.out.println(intersectionNode.val);
+        }else{
+            System.out.println("没有相交的节点哦");
+        }
+
+    }
+}
diff --git a/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution7.java b/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution7.java
@@ -0,0 +1,71 @@
+package com.algorithm.study.demo.algorithm.leetcode;
+
+/**
+ * @author xun2.liu
+ * @title: Solution7
+ * @projectName algorithm-study
+ * @description: 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
+ *
+ * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
+ *
+ * 说明：不允许修改给定的链表。
+ *
+ * 示例 1：
+ *
+ * 输入：head = [1,2], pos = 0
+ * 输出：tail connects to node index 0
+ * 解释：链表中有一个环，其尾部连接到第一个节点。
+ *
+ * 来源：力扣（LeetCode）
+ * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
+ *
+ * @date 2020/5/19 17:16
+ */
+public class Solution7 {
+    public static class ListNode {
+        int val;
+        ListNode next;
+        ListNode(int x) { val = x; }
+    }
+
+    /**
+     * 快慢指针遍历连表。看是否相遇。如果相遇在判断是否是循环链表。
+     * @param head
+     * @return
+     */
+    public static ListNode detectCycle(ListNode head) {
+        if (null== head || head.next==null){
+            return null;
+        }
+        ListNode p1=head;
+        ListNode p2=head;
+        while(p2!=null && p2.next!=null){
+            p1=p1.next;
+            p2=p2.next.next;
+            if(p1==p2){
+                break;
+            }
+        }
+        if (p1!=p2){
+            return null;
+        }
+        p1=head;
+        while(p1!=p2){
+            p1=p1.next;
+            p2=p2.next;
+        }
+        return p1;
+    }
+    public static void main(String[] args) {
+        ListNode a=new ListNode(5);
+        ListNode b=new ListNode(4);
+        ListNode c=new ListNode(6);
+        ListNode d=new ListNode(-1);
+        a.next=b;
+        b.next=c;
+        c.next=b;
+//        c.next=b;
+        ListNode listNode = detectCycle(a);
+        System.out.println(listNode==null?"":listNode.val);
+    }
+}
