2015年9月1日星期二

LintCode: Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Have you met this question in a real interview? 
Yes
Example
Given -21->10->4->5, tail connects to node index 1, return true
Challenge
Follow up:
Can you solve it without using extra space?
Tags Expand 
Two Pointers Linked List

Thought:
next pointer cannot point to nodes that appear before current node.

Hashmap solution:
Time: O(n)
Space: O(n)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode *head) {
        // write your code here
        set<ListNode*> record;
        while(head){
            if(record.count(head)) return true;
            record.insert(head);
            head = head->next;
        }
        return false;
    }
};
Two pointers solution:
If we have two pointers:: fast and slow. It's guaranteed that the fast one will catch up with the slow pointer again if there exists a cycle.
Time: O(n)
Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow && fast){
            if(slow->next != NULL){
                slow = slow->next;
            }else break;
            if(fast->next != NULL){
                fast = fast->next;
            }else break;
            if(fast->next != NULL){
                fast = fast->next;
            }else break;
            
            if(slow == fast) return true;
        }
        return false;
    }
};

Well, codes are succinct enough. 
Modified version:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != NULL && fast->next->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) return true;
        }
        return false;
    }
};


Lintcode second:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    bool hasCycle(ListNode *head) {
        // write your code here
        ListNode *slow, *fast;
        slow = fast = head;
        while(slow && fast && slow->next && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)