LeetCode 141、142环形链表

测试账号 2021-01-10 15:38 588阅读 0赞

**141题：**

首先，先看141题，这个题是比较初级也是比较经典的环形链表题：

给定一个链表，判断链表中是否有环。

进阶：  
你能否不使用额外空间解决此题？

那么，什么是有环的链表呢：

![1372758-20181204162438386-1860314436.png][]这个就是有环的链表

题设中说，能否不使用额外空间解决此题，说明，最普通的方法就是用其他的数据结构解决这个问题，那么我们想把链表结点依次遍历放入哈希表中，然后遇到重复的结点说明是有环的，这就是利用了其他的额外空间来解决这个问题，空间复杂度为O(n)，现在我们直接说进阶的思路：

**思路**

**如果，在环形的跑道上跑步的话，跑的快和跑的慢的人一直跑，会出现什么情况：**

**肯定是会相遇的，那么该题的解题思路就是：**

**龟兔赛跑法**

**快慢指针往前走，慢指针每次走1步，快指针每次走2步，如果是有环，快慢指针会相遇，否则永远不会相遇**  
**空间复杂度:O(1)，时间复杂度：O(n)**

**上代码：**

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    /**
     * 解题思路:龟兔赛跑法
     * 快慢指针往前走，慢指针每次走1步，快指针每次走2步，如果是有环，快慢指针会相遇，否则永远不会相遇
     * 空间复杂度:O(1)，时间复杂度：O(n)
     */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while(slow != null && fast !=null && fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    return true;
                }
            }
            return false;
        }
    }

是不是觉得很神奇而且很简单呢，哈哈，接下来让我们看142第二题：

**142题：**

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

说明：不允许修改给定的链表。

进阶：  
你是否可以不用额外空间解决此题？

入环的第一个节点？感觉没有什么头绪能够捕捉到这个节点，让我们多分析分析这个环形链表

![1372758-20181204170907655-825180651.png][]

设：

链表总长度: len  
　　起点到入环的第一个节点的距离 ： a               环起点到相遇点的距离：b                相遇点到环起点的距离：c  
　　快节点绕环的圈数：k，                                   环的长度：r，                                  慢指针一共走的距离：s，慢指针一共走的距离：2s  
则：  
s + kr = 2s => s = kr    因为s = a + b; => a + b = kr  
=>a + b = (k-1)r + r = (k - 1)r + len - a => a = (k - 1)r + len - a - b  
=> a = (k-1)r + c  
说明 从头结点和从相遇点以相同的速度向前移动，总会相交在环起点，如图所示，即从3点出发和从1点出发，速度一样的话，总会相遇在2点。

那我们将快节点指向head节点，然后一次走一步，慢结点不变，那么，他们相遇的地方就是环的头结点。

上代码：

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null)
                return null;
            ListNode slow = head;
            ListNode fast = head;
            while(fast!=null&&fast.next!=null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    break;
                }
            }
            if(fast == slow){
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }else{
                return null;
            }
            
        }
    }

是否感受到了算法的奇妙之美，哈哈，加油！

[1372758-20181204162438386-1860314436.png]: /images/1610293099799.png
[1372758-20181204170907655-825180651.png]: /images/1610293081523.png