当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

Leectode142. 环形链表 II🌟🌟🌟🌟中等

算法系统课 免费

课后作业

问题描述

原文链接：142. 环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

img

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

代码实现

Java

/**
 * 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 == head){
            return head;
        }
        // 
        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;
        }
        //统计环的节点个数
        int n = 1;
        while(true){
            fast = fast.next;
            if(fast == slow){
                break;
            }
            n++;
        }
        ListNode pre = head;
        ListNode last = head;
        // last先走n步
        for(int i = 0; i < n; i++){
            last = last.next;
        }
        while(true){
            if(last == pre){
                return pre;
            }
            last = last.next;
            pre = pre.next;
        }
    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if(head == None or head.next == head):
            return head
        # 
        fast = head
        slow = head
        while(fast != None and fast.next != None):
            fast = fast.next.next
            slow = slow.next
            if(fast == slow):
                break
        if(fast == None or fast.next == None):
            return None
        #统计环的节点个数
        n = 1
        while(True):
            fast = fast.next
            if(fast == slow):
                break
            n += 1
        pre = head
        last = head
        # last先走n步
        for i in range(n):
            last = last.next
        while(True):
            if(last == pre):
                return pre
            last = last.next
            pre = pre.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == head){
            return head;
        }
        // 
        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;
        }
        //统计环的节点个数
        int n = 1;
        while(true){
            fast = fast->next;
            if(fast == slow){
                break;
            }
            n++;
        }
        ListNode* pre = head;
        ListNode* last = head;
        // last先走n步
        for(int i = 0; i < n; i++){
            last = last->next;
        }
        while(true){
            if(last == pre){
                return pre;
            }
            last = last->next;
            pre = pre->next;
        }
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == head {
        return head
    }
    // 
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    //统计环的节点个数
    n := 1
    for {
        fast = fast.Next
        if fast == slow {
            break
        }
        n++
    }
    pre := head
    last := head
    // last先走n步
    for i := 0; i < n; i++ {
        last = last.Next
    }
    for {
        if last == pre {
            return pre
        }
        last = last.Next
        pre = pre.Next
    }
}

发表回复

后才能评论

评论(6)

  • 少年不识流川枫 永久会员 2024年2月28日 上午12:48 
    public class Solution {
    public ListNode detectCycle(ListNode head) {
         if(head == null || head.next == null){
            return null;
        }

        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;
        }else{
            // 计算环的个数n
            int n = 1;
            while(true){
                fast = fast.next;
                if(fast == slow){
                    break;
                }
                n++;
            }
        ListNode pre = head;
        ListNode last = head;
        //last走环的个数步，即是上面的n
        for(int i = 0; i < n; i++){
            last = last.next;
        }
        while(last != null && last.next != null){
            if(pre == last){
                return pre;
            }
            pre = pre.next;
            last = last.next;
        }}
        return null;
    }
}

    最后写的略微啰嗦一点

  • Yuki 永久会员 2024年1月31日 上午10:01

    打卡
    class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
    //排除空链表和只有一个节点的情况
    if(headNULL||head->nextNULL)
    return NULL;

        ListNode*slow=head;
    ListNode*fast=head;
    int count=0;

    while(fast!=NULL&&fast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
        count++;

        if(fast==slow){
        //快慢指针相遇，说明有环，找相遇节点
            ListNode*cur1=head;
            ListNode*cur2=fast;
            while(cur1!=cur2){
                cur1=cur1->next;
                cur2=cur2->next;
            }
            return cur1;
        }
    }
    return NULL;
}

    };
    /*
    思路：
    1、先判断是否有环，再找入口节点
    2、从头结点出发一个指针，从相遇节点也出发一个指针，
    这两个指针每次只走一个节点，相遇处为入口节点
    */

  • uu 永久会员 2023年9月20日 下午4:55 
    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// 【思路】快慢指针
// 时间复杂度：O(4n)->O(n)
// 空间复杂度：O(1)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        int pre = 0;
        int sub = 0;


        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            pre += 2;
            sub += 1;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }

        int circle = pre - sub;

        fast = head;
        slow = head;
        for(int i =0; i < circle; i++) {
            fast = fast.next;
        }
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

// 【思路】哈希表
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// public class Solution {
//     public ListNode detectCycle(ListNode head) {
//         Set visited = new HashSet();
//         ListNode ans = head;
//         while(ans != null) {
//             if(visited.contains(ans)) {
//                 return ans;
//             }
//             else {
//                 visited.add(ans);
//             }
//             ans = ans.next;
//         }
//         return null;
//     }
// }
  • 泡芙 永久会员 2023年9月8日 下午4:41

    方法一：

    ①统计环节点个数（没环就不统计）

    以初次相遇为起点，slow不动，fast继续走，再次相遇时fast走过的节点为n

    ②last先走n步，然后和pre一起走，再次相遇就是环入口

    public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        // 找初次相遇的节点
        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;
        }

        // 初次相遇为起点统计节点n
        int n = 0;
        while (true) {
            fast = fast.next;
            n ++;
            if (fast == slow) {
                break;
            }           
        }

        // 再次相遇的节点为环入口
        ListNode pre = head;
        ListNode last = head;
        // last先走n步
        for (int i = 0; i < n; i ++) {
            last = last.next;
        }

        while (true) {
            if (last == pre) {
                return pre;
            }
            pre = pre.next;
            last = last.next;
        }
    }
}

    方法二：

    不统计节点，只需要两个指针

    先快慢指针第一次相遇时，slow定位在初次相遇节点，fast重新定位到head节点，此时fast和slow一起走，当再次相遇时，fast为环入口

    • Time：O(n)
    • Space：O(1）
    public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        // 找初次相遇的节点
        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;
        }

        // fast从头走,和slow一起走，再次相遇即为环入口
        fast = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
  • 阿尚 普通 2023年8月18日 下午1:57 
    public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;

        ListNode f = head;
        ListNode s = head;

        while(f != null && f.next != null){
            f = f.next.next;
            s = s.next;
            //存在环路
            if(f == s){
                s = head;
                while(s != f){
                    s = s.next;
                    f = f.next;
                }
                return s;
            }
        }

        return null;
    }
}
  • 帅气的冬瓜 普通 2023年6月28日 下午5:33

    打卡

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理