FAQ: Technical Interview Problems in Python: Linked Lists - Detect Cycle in a Linked List

Frequently Asked Questions Python FAQ
1

Community%20FAQs%20on%20Codecademy%20Exercises
Community%20FAQs%20on%20Codecademy%20Exercises1000×208 141 KB

This community-built FAQ covers the “Detect Cycle in a Linked List” exercise from the lesson “Technical Interview Problems in Python: Linked Lists”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Technical Interview Practice: Python

FAQs on the exercise Detect Cycle in a Linked List

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

2

would you show me the logic of the lesson’ task:

why does the code:

def has_cycle(linked_list):
  slow, fast = linked_list.head, linked_list.head
  while slow and fast:
    slow = slow.next
    fast = fast.next
    if fast:
      fast = fast.next
    else:
      return False
    print(fast,"!",slow)
    print(fast.val,"!!!",slow.val)
    print("")
    if fast == slow:
      return True
  return False

returns True, when node ‘b’ (fast)== node ‘c’ (slow)
and doesn’t return True, when 'node ‘d’ (fast) equals node ‘d’ (slow)

to illustrate the computing process, I put prints in the middle of the loop:

<node.Node object at 0x7f3290c5f898> ! <node.Node object at 0x7f3290c5f7b8>
c !!! b

<node.Node object at 0x7f3290c5f7b8> ! <node.Node object at 0x7f3290c5f898>
b !!! c

<node.Node object at 0x7f328f935828> ! <node.Node object at 0x7f328f935828>
d !!! d

<node.Node object at 0x7f328f935ba8> ! <node.Node object at 0x7f328f935a20>
c !!! b

<node.Node object at 0x7f328f935c18> ! <node.Node object at 0x7f328f935ba8>
b !!! c

Should return True when a cycle exists: True
3

Hi,

Here is my solution 
from linked_list import LinkedList, Node, build_cycle_linked_list, build_linked_list_no_cycle


cycle_linked_list = build_cycle_linked_list()
no_cycle_linked_list = build_linked_list_no_cycle()

def has_cycle(linked_list):
  current_node = linked_list.head
  unique = []
  
  while current_node:
    node_id = id(current_node)
    if node_id in unique:
      return True
    else:
      unique.append(node_id)
    current_node = current_node.next

  return False

cycle_result = has_cycle(cycle_linked_list)
no_cycle_result = has_cycle(no_cycle_linked_list)

print("Should return True when a cycle exists: {0}".format(cycle_result))

print("Should return False when a cycle does not exist: {0}".format(no_cycle_result))

I have a question: Is it better to use dictionary instead of list?
I use list, because we don’t have to store as key-value pair, but to find a key in a dictionary is O(1) time, in list O(N)…
So maybe better to choose dictionary even if I not use as a key-value?

1 Like