首页 > ACM题库 > LeetCode > LeetCode-Linked List Cycle[链表]
2014
11-18

LeetCode-Linked List Cycle[链表]

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

标签: Linked List Two Pointers
分析

最容易想到的方法是,用一个哈希表{unordered_map<int, bool> visited},记录每个元素是否被访问过,一旦出现某个元素被重复访问,说明存在环。空间复杂度$O(n)$,时间复杂度$O(N)$。

最好的方法是时间复杂度$O(n)$,空间复杂度$O(1)$的。设置两个指针,一个快一个慢,快的指针每次走两步,慢的指针每次走一步,如果快指针和慢指针相遇,则说明有环。参考{ http://leetcode.com/2010/09/detecting-loop-in-singly-linked-list.html}

代码1

//LeetCode, Linked List Cycle
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 设置两个指针,一个快一个慢
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

Java代码:

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

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。