Wednesday, February 6, 2013

Linked List Reverse circular way

Following code attempts to reverse a singly linked list in a circular fashion, for example, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7  to 7 -> 1 -> 6 -> 2 -> 5 -> 3 -> 4


There are other ways to achieve this output in much efficient way but I just thought of posting this naive one O(n * n).

public void reverseSpecial(Node node) {
        Node temp = node;
        Node endbefore = null;
        Node head = temp;
        Node newstart = null;
        while (head != null && head.next != null) {
            while (temp != null && temp.next != null) {
                endbefore = temp;
                temp = temp.next;
            }
            if (newstart == null) { //first time
                newstart = temp;
            }
            temp.next = head;
            temp = head.next;
            head.next = endbefore;
            head = temp;
            endbefore.next = null;
        }

No comments:

Post a Comment