1
$\begingroup$

I have pointer to circular doubly linked list with random values of 0 or 1.
Example: [{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]
I have a single pointer to the first item of the list. I need to find the length of the list without to create any additional pointers.
In addition, I can change the values of each node between 0 to 1 or 1 to 0.

I thought about Josephus Circle algorithm - with no success.

My main problem is that I don't even know what end of a circle/circular list is.
If you think about that, you will understand it is not an easy question.

Improve this question
$\endgroup$
9
  • $\begingroup$ (I don't know if I arrive to the end of the list I don't even know what end of a circle/circular list is.) You may need to change direction, not limited to your thinking. It may help to think of Turing. $\endgroup$
    – greybeard
    Commented Apr 25, 2019 at 23:35
  • $\begingroup$ @greybeard I changed the direction. How can Turing help here? $\endgroup$
    – motis10
    Commented Apr 25, 2019 at 23:38
  • $\begingroup$ Are you looking for any algorithm at all, no matter how efficient? Do you have requirements on how efficient it must be? Do you have a pointer to the start of the list (so you can keep a pointer to the start of the list and a separate pointer that you modify)? $\endgroup$
    – D.W. ♦
    Commented Apr 25, 2019 at 23:55
  • $\begingroup$ I have a single pointer to the start of the list. But I can't add separate pointer. The efficienct should be the best it can $\endgroup$
    – motis10
    Commented Apr 26, 2019 at 0:00
  • $\begingroup$ Sorry, I don't understand. Can you have one pointer that is to the start of the list and is never modified but can be read later, and a second pointer that you modify in each step of the algorithm? Can you tell us where you encountered this problem? Can you credit the original source of the problem? $\endgroup$
    – D.W. ♦
    Commented Apr 26, 2019 at 0:21

2 Answers 2

Reset to default
1
$\begingroup$

I think the following algorithm would do it:

  1. Start by setting the value in the first node to $1$.
  2. Follow next pointers until you encounter a node with value $1$, while keeping a counter $c$ of how many nodes you have encountered.
  3. Set the value of the node to $0$ and follow prev pointers for $c$ steps
    • If the value of the node (which should be the first node) is now $0$, the list has $c-1$ elements,
    • otherwise, follow next pointers for $c$ steps and continue with step 2.
Improve this answer
$\endgroup$
4
  • $\begingroup$ @D.W. Are you sure? It's looks promising as you said. $\endgroup$
    – motis10
    Commented Apr 26, 2019 at 16:29
  • $\begingroup$ @motis10, I was confused. Sorry. $\endgroup$
    – D.W. ♦
    Commented Apr 26, 2019 at 16:31
  • $\begingroup$ @AcId and complexity is O(n(n+1)) = O(n^2). Right? $\endgroup$
    – motis10
    Commented Apr 26, 2019 at 18:12
  • $\begingroup$ In the worst case (when every node has value $1$) you cycle back an forth across the list in every step, so I would say that the worst time complexity is $\sum_{i = 1}^n 2 i = n (n + 1) = \mathcal{O}(n^2)$. In the best case (every node has the value $0$) we only go back through the list once, so the best case complexity is $2n$. $\endgroup$
    – AcId
    Commented Apr 26, 2019 at 18:15
0
$\begingroup$

One of your comments suggests that you are interested in an ‘efficient’ solution -
assuming a non-empty list correctly doubly linked:

  0. let $toSet = 1$ and set current item to $0$

  1. $toSet$ times, follow the $next$ link and set to $1$
  2. $toSet - 1$ times, follow the $prev$ link
  3. up to $toSet$ times,
    • follow the $prev$ link,
    • if item is $1$, the number of $prev$s followed since last change of direction is the number of items,
      else set to $1$
  4. double $toSet$
  5. $toSet$ times, follow the $prev$ link and set to $0$
  6. $toSet - 1$ times, follow the $next$ link
  7. up to $toSet$ times,
    • follow the $next$ link,
    • if item is $0$, the number of $next$s followed since last change of direction is the number of items,
      else set to $0$
  8. double $toSet$ and repeat from 1

The number of items set and potentially inspected doubles with each "half-iteration".
The number of items checked is exactly the number $n$ of items in the list.
The number of items set varies from $3n-1$ for $n = 2^i$ to $2n$ for $n = 2^{i + 1} - 1$.

ToDo: find
a simple pattern of length growth between ("half-")iterations that works for every list length, too, and
a list length where #sets + #follows + #compares is smaller than for doubling as above

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ I do not believe your algorithm is correct. Running the algorithm on an example with a list of size $3$ gives the result $2$ in step $7)$. $\endgroup$
    – AcId
    Commented Apr 28, 2019 at 11:16
  • $\begingroup$ @AcId: I had translated this to and from Java before posting. While 3 hasn't been one of my test cases, 1, 7, 8 and 9 were, in addition to larger ones. Just added 3 with no problem - how can we sort this out? $\endgroup$
    – greybeard
    Commented Apr 28, 2019 at 19:58
  • $\begingroup$ (Hm. One point where I thought I might/would get overly explicit is number of $prev$s/$next$s followed: since last change of direction, not start of procedure.) $\endgroup$
    – greybeard
    Commented Apr 28, 2019 at 20:36
  • 1
    $\begingroup$ Perhaps the Java code doesn't match what you've written here, as I also get a result 2 when running on a list of size 3. First we do lines 0-3, and the list is [1,1,x]. After line 4, toSet = 2. After line 6, the list is [1,0,0], and we're pointing at the last item in the list. Step 7 first sets the list to [0,0,0], then terminates after following the second next link, and outputs 2. $\endgroup$
    – D.W. ♦
    Commented Apr 29, 2019 at 1:01
  • 1
    $\begingroup$ @greybeard : So in step $3$ (resp. $7$) you have to also count the links followed in step $2$ (reps. $6$)? I don not think this is very clear from your answer. Perhaps consider editing to make this point clear. $\endgroup$
    – AcId
    Commented Apr 29, 2019 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.