[LeetCode] 142. Linked List Cycle II 链表中的环 II

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 142. Linked List Cycle II 链表中的环 II,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.html

Follow up:
Can you solve it without using extra space?java

141. Linked List Cycle 的拓展,这题要返回环开始的节点,若是没有环返回null。node

解法:双指针,仍是用快慢两个指针,相遇时记下节点。参考:willduan的博客python

Java:post

public class Solution {  
    public ListNode detectCycle( ListNode head ) {  
        if( head == null || head.next == null ){  
            return null;  
        }  
        // 快指针fp和慢指针sp,  
        ListNode fp = head, sp = head;  
        while( fp != null && fp.next != null){  
            sp = sp.next;  
            fp = fp.next.next;  
            //此处应该用fp == sp ,而不能用fp.equals(sp) 由于链表为1 2 的时候容易  
            //抛出异常  
            if( fp == sp ){  //说明有环  
                break;  
            }  
        }  
        //System.out.println( fp.val + "   "+ sp.val );  
        if( fp == null || fp.next == null ){  
            return null;  
        }  
        //说明有环,求环的起始节点  
        sp = head;  
        while( fp != sp ){  
            sp = sp.next;  
            fp = fp.next;  
        }  
        return sp;  
    }  
}   

Python:url

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def __str__(self):
        if self:
            return "{}".format(self.val)
        else:
            return None
        
class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast is slow:
                fast = head
                while fast is not slow:
                    fast, slow = fast.next, slow.next
                return fast
        return None  

C++:spa

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        if (!fast || !fast->next) return NULL;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

  

相似题目:.net

[LeetCode] 141. Linked List Cycle 链表中的环指针

 

All LeetCode Questions List 题目汇总