Skip to content

Instantly share code, notes, and snippets.

@c02y
Created May 16, 2020 01:43
Show Gist options
  • Save c02y/ec0042a1ba6b617920b8a52ee2fd45b4 to your computer and use it in GitHub Desktop.
Save c02y/ec0042a1ba6b617920b8a52ee2fd45b4 to your computer and use it in GitHub Desktop.
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")
@c02y
Copy link
Author

c02y commented May 16, 2020

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;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment