3

From Cracking the Coding Interview, there is an exercise that says:

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

Definition of circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.

The algorithmic answer is basically using a slow and fast runner to iterate through the linked list to see if it loops. If the slow and fast runner collide, it loops, so then you find the node at the beginning of the loop. (If they don't collide, then the fast runner will eventually reach the end of the linked list, meaning there is no cycle.)

But the book's answer for finding where the node at the beginning of the loop is relies on the ASSUMPTION that the linked list has a "non-looped" part of size k. Once the slow and fast runners collide, you move the slow runner to the head of the linked list. You iterate both at the same speed until they collide. Where they collide is the node at the beginning of the loop.

My question is, is it possible to find where the node at the beginning of the loop is WITHOUT assuming the linked list has a "non-looped" part of size k? Or do I have to assume that there is a "non-looped" part of size k?

Jessica
  • 1,083
  • 2
  • 12
  • 27
  • You can answer yourself. Consider a list of size `n`. The sise of the loop can be `k ` with `0 <= k <= n` and starting at `i` with `0 <= i < n` Think of cases `k = 0` and `k = n` and where runners end. – Ripi2 Aug 23 '18 at 23:32
  • "There is no non looped part of size k" <==> "There is a non looped part of size k, k =0" <==> "The entire linked list is a cycle" <==> "Fast and slow runners has already collided" <==> "First node of list is first node of cycle". That being said if you are worried abt the init condition, you can modify floyd's algo to dtect the first time they collide after the init step. If the collision node is the same as the init node then *k* = 0 – Srini Aug 23 '18 at 23:36
  • 1
    How do you even *define* "the beginning of the loop" if there's no "non-looped" part? Do you mean the first node? – ruakh Aug 24 '18 at 00:01
  • what is the structure of this *linked-list*? I believe the beginning node is the only node which has two node point to it. otherwise there is no *beginning* at all. – apple apple Aug 24 '18 at 01:19
  • or does it have any time/space constraint? – apple apple Aug 24 '18 at 01:22

3 Answers3

2

I have 2 answers for this question,
One:
If you have loop inside the list in size k, if you move one of the pointer k steps from the head and another pointer from the head and move them together, finnally when one of them do a full loop, and the another one just start the loop, and then this the reason they both meet at the begining of the loop. all you need is count the nodes on the loop.
Second:
I intreduce my solution by example:
assume we got this list: list.
find a common pointer using the faster and slower runner method. let's assume that they meet in node number 7. after you do it remmber the next pointer of node 7 (as the end of the list). and for now we can reduction to another problem for solve this problem and that is finding first common element in two linked lists that the end of them is pointer of "node 8", and the head of one of them is the head of the list (node 0) and for the other list head is "node 8".
it's look like this: this.

you can solve it by the following steps:
1) Get count of the nodes in the first list, let count be c1.
2) Get count of the nodes in the second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes).

Ripi2
  • 7,031
  • 1
  • 17
  • 33
assaf.b
  • 124
  • 1
  • 1
  • 10
1

Unless the book specifically assumes the existence of a positive such k, k can also be zero.

Here's an informal argument for the case k=0:

Assume that the entire list is a loop.
If the fast runner is twice as fast as the slow runner, they will collide when the slow runner has completed one loop, and the fast runner has completed two.
If you then start the slow runner from the beginning again, the two will collide immediately on the first node.

molbdnilo
  • 64,751
  • 3
  • 43
  • 82
0

I'm not familiar with that book, but I don't think you read it right. Probably k is the size of the loop, and the algorithm works like this:

  1. Detect a loop using either Floyd's or Brent's algorithm. (both are described here: https://en.wikipedia.org/wiki/Cycle_detection)
  2. Let k be the a multiple of the size of the loop, so that once you're in the loop, you'll get back to the same node if you make k steps. You can measure this after you find the cycle, or you can just count the difference in steps between the "fast pointer" and the "slow pointer" while looking for the cycle.
  3. Put 2 pointers at the head of the list (call them fast and slow again), and advance the "fast" pointer k times.
  4. While the fast and slow pointers point at different nodes, advance them in lock step, so that the fast pointer is always k steps ahead.

The algorithm will stop as soon as the slow pointer gets into the loop -- the first node that can be reached again by advancing through the list.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • I also thought I read the book wrong, but it says the non-looped portion is of length k. But thank you for mentioning this new method of finding the node at the beginning of the looped portion. – Jessica Aug 26 '18 at 02:16