CODEWITHSUNDEEP
algorithmdata-structuresdoubly-linked-list
Abhinav Raut
Abhinav Raut

Reputation: 31

Is it possible to reverse a doubly circular linked list? if Yes, then how?

I am a bit confused, as one of my friend said it not possible. As it's totally symmetric.

I have googled a bit but I am still confused

Upvotes: 1

Views: 1249

Answers (3)

Daniel
Daniel

Reputation: 7724

For each node N of the list, you just need to swap N.next and N.prev. After this, you change the reference of head to be the new head.next. If there is a tail, it should be updated to tail.prev.

Just for better visualization:

enter image description here

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

It is not impossible, it might require some extra care to design the algorithm, but that is with most (all) algorithms where you have to iterate and modify the data structure.

You can simply swap the head and tail, and then iterate over your linked list and swap the next and previous references for each node. You furthermore need to make sure you stop doing that after one full iteration.

A sample algorithm in Python would look like:

class CircularDoubleLinkedList:

    # ...

    def reverse(self):
        self.head, self.tail = self.tail, self.head
        start = cur = self.head
        if cur is not None:
            cur.next, cur.previous = cur.previous, cur.next
            cur = cur.previous
        while cur is not None and cur is not start:
            cur.next, cur.previous = cur.previous, cur.next
            cur = cur.previous  # move to the next node

Upvotes: 2

Prune
Prune

Reputation: 77847

Yes; simply swap the previous and next pointers, as well as any head and tail pointers. Can you explain how your friend claims that the list is symmetric?

Upvotes: 2

Related Questions