算法：链表之环形链表

灰子学技术

发布于 2020-07-29 14:37:14

3270

发布于 2020-07-29 14:37:14

文章被收录于专栏：灰子学技术灰子学技术

算法：

该类题目的核心点在于如何判断是环形链表，核心思想是：两个人在环上跑步，跑的快的早晚会追上跑的慢的。

是快慢指针的典型使用场景。

题目1: 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow := head // 慢指针一次走一步
    fast := head.Next // 快指针一次走两步
    for slow != fast {
        if slow == nil || fast == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next
        if fast != nil {
            fast = fast.Next
        }
    }
    return true
}

执行结果：

题目2:

https://leetcode-cn.com/problems/linked-list-cycle-lcci/

代码实现：

// 算法：该题目主要分两步，第一步是找到环形链表中的相交的位置。
// 第二步是让慢指针指向链表首部，快指针位置不变，
// 然后快慢指针每次都走一步，再次相遇就是环形链表的入口位置。
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    s, f := head,head
    for f != nil && f.Next != nil { 
        s = s.Next
        f = f.Next.Next
        if f == s { // 判断是不是有环
            break
        }
    }
    if f == nil || f.Next == nil { 
        // 此时的快指针在环里面，理论上这两个都不应该为空；
        // 只有一个节点的话,f.Next == nil
        return nil
    }

    s = head 
    for s != f {
        s = s.Next
        f = f.Next
    }
    return s
}

执行结果：