CODEWITHSUNDEEP
javarecursionprintinglinked-list
Donald
Donald

Reputation: 1340

Print a Circular Linked List Recursively

I have been stumped by this question in one of my tutorials:

Given a Circular linked list which has only a tail pointer, write a recursive method with the following header to print out the list recursively starting from the first element:

public void circularPrint()

I could easily do this question had it not stated to print out the list starting from the first element. But I am stumped because of the multiple restrictions that are enforced by this question. Could someone please advise me on how to solve this problem?

Thank you.

Upvotes: 0

Views: 2387

Answers (3)

Sylwester
Sylwester

Reputation: 48745

Is the list only one circle, like a circular buffer? Then you can print until the next pointer is the same as the reference to the list.

If the circles can be in to any previous element then you need to apply one of the Turtoise and hare algorithms.

It's quite easy with singly linked lists. Not so easy if you have like Scheme cons cells that can have structure in both pointers which would require quite a bit of backtracking and housekeeping.

As for you problem with the method signature I haven't heard of inner methods in Java so you'll need to define a helper. eg.

public void circularPrint()
{
  circularPrintAux(this);
}

For turoise and hare it would be:

public void circularPrint()
{
  if( this.next == this )
      ...
  else
      circularPrintAux(this, this.next);
}

Upvotes: 1

Eel Lee
Eel Lee

Reputation: 3543

If it's circular linked list, that means that the last element (tail) has a field pointing to the first element. So at this moment you also have a head (so to speak).

You can do it for example this way:

  1. Print the tail's next element (which is the 1-st element).
  2. Assign the second element to the tail's next.
  3. Repeat.

Upvotes: 1

Michael Hoyle
Michael Hoyle

Reputation: 239

You will need to pass in two parameters, the current element and the starting element. For your first call, these will be the same. Once you've printed the current element, recursively call on the next element in the list. Only do the recursive call if the next element != the starting element.

Upvotes: 0

Related Questions