LinkedListCycle.py

LinkedListCycle.py

# 141. Linked List Cycle (Easy)
# https://leetcode-cn.com/problems/linked-list-cycle/description/

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

class Solution:
    def __init__(self):
        self.root = None

    def addNode(self, root, numbers, index, size):
        if index < size:
            temp = ListNode(numbers[index])
            root = temp
            root.next = self.addNode(root.next, numbers, index + 1, size)
            # the following line make tail point to the head which make root a loop
            # uncomment it again to see the result
            # root.next = temp
        return root

    def hasCycle(self, head: ListNode) -> bool:
        one = head
        two = head

        while one and two and two.next:
            one = one.next
            two = two.next.next
            if one == two:
                return True
        return False


if __name__ == '__main__':
    numbers = [3, 2, 0, -4]
    solu = Solution()
    root = solu.addNode(solu, numbers, 0, len(numbers))

    print("Loop" if Solution().hasCycle(root) else "Non-loop")

Cpp version:

// 141. Linked List Cycle (Easy)
// https://leetcode-cn.com/problems/linked-list-cycle/description/
#include <iostream>
#include <vector>

// Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	bool hasCycle(ListNode *head) {
		ListNode * one = head;
		ListNode * two = head;

		while (one && two && two->next) {
			one = one->next;
			two = two->next->next;
			if (one == two)
				return true;
		}
		return false;
	}
};

int main()
{
	std::vector<int> head{3, 2, 0, -4};

	int i = 0;
	ListNode * node = new ListNode(head[i++]);
	ListNode * tmp = node;
	while (i < head.size()) {
		tmp = tmp->next = new ListNode(head[i++]);
	}
	std::cout << (Solution().hasCycle(node) ? "Loop" : "Non-loop") << std::endl;

	tmp->next = node;       // tail points to head
	std::cout << (Solution().hasCycle(node) ? "Loop" : "Non-loop") << std::endl;

	return 0;
}