Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Start of LinkedList Cycle (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
  def findCycleStart(self, head):
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      // when the two pointers meet, rest anyone pointer back to head and then step one at a time
			// until they meet again. the point they meet is the starting of the cycle.
      if slow == fast:
        slow = head
        while slow!=fast:
          slow = slow.next
          fast = fast.next
        return slow
    return None
A

Anonymous

· 2 years ago

Why we need to use slow/fast pointer approach while we can just store some unique value of each node? In c++ we can use memory address.

It is simply O(n), because we iterate over all list but we have also O(n) memory for HashSet.

Algorithm is simple. We need to iterate and add each pointer to hashSet until we come across already added one. Then return pointed address.

Code:

ListNode *findCycleStart(ListNode *head) {
    std::unordered_set<ListNode*> visitedNodes;    
    ListNode* it = head;

    do
    {
      visitedNodes.insert(it);
      it = it->next;
    }while(!visitedNodes.contains(it));
    
    return it;
}
Show 1 reply
A

Anonymous

· 2 years ago

Here is the solution that is clean and 100% be the official solution

class Solution:
  def findCycleStart(self, head):
    slow, fast = head, head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if fast == slow:
        break
    slow = head
    while slow != fast:
      fast = fast.next
      slow = slow.next
    return slow
A

Anonymous

· 2 years ago

Good job on this course, Design Guru. However, LeetCode has published a more concise solution (in java).

// Design Guru Problem Statement: Start of LinkedList Cycle
// LeetCode Question: 142. Linked List Cycle II
public class Problem_3_Start_Of_LinkedList_Cycle {
    class ListNode{
        int val = 0;
        ListNode next;

        public ListNode(int value){
            this.val = value;
        }
    }

    public ListNode findCycleStart(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == head) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
Show 1 reply
A

Anonymous

· 3 years ago


#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def findCycleStart(self, head):
    #TODO Write your code here
    if head == None or head.next == None:
      return None
    slow, fast = head, head
    while fast != None and fast.next != None:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
        slow = head 
        while slow != fast:
          slow = slow.next
          fast = fast.next
        return slow
    return None

I feel like if you don't refine this code, this course is not even worth the money I am paying

Show 1 reply
A

Anonymous

· 3 years ago

very important combination of these

A

Anonymous

· 3 years ago

"As pointer2 is ‘K’ nodes ahead of pointer1, which means, pointer2 must have completed one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle."

But WHY must their meeting point be the start of cycle? I get that pointer2 is k nodes ahead of pointer1 and that when both pointers meet, pointer2 will b k nodes in the cycle but why does that mean it'll be the start of cycle?

A

Anonymous

· 3 years ago

The task states "Given the head of a Singly LinkedList that contains a cycle" but one of the test cases fails with my code with a NoneType exception when executing "fast = ".

It seems that or is None but if the list indeed has a cycle in it, then every node would have to have a next node or am I missing something?

I see two possible scenarios:

a) There are test cases where the input list does not contain a cycle.

  • Do others feel that the phrasing of the task is misleading as well?
  • What should the return value be in that case, since there is no beginning of a cycle if there is no cycle?

b) All test cases contain a cycle

  • How can ever be None if there is a cycle?

Note:

  1. I can't add the code directly here because if I save it without using the code block it loses the li
Show 1 reply
A

Anonymous

· 3 years ago

3 methods. I Liked 2nd.

While iterating over Nodes, modify every nodes and point them towards temporary variable. If there is loop, you will come back to the Node that is pointing towards temporary variable. That's the Node you are finding! https://www.geeksforgeeks.org/find-first-node-of-loop-in-a-linked-list/

Show 1 reply
A

Anonymous

· 4 years ago

Frankly i'm not 100% sure how this example builds on any previous experience. I guess it's sort of related in that you know how to detect a cycle by this point and can iterate until that's done but the logical jump between that and the Floyd's Tortoise and Hare algorithm seems extreme.

Show 1 reply

Reading Progress

0%

Vote for new content