CareerCup

There can be various methods to reverse a linked list, but here we can take advantage of it being a doubly linked list:

1. loop from head to tail. For each node swap next and prev.

for(p = head;p!=NULL;p=r)
{
r=p->next;
p->next=p->next^p->prev;
p->prev=p->next^p->prev;
p->next=p->next^p->prev;
}

2.swap head and tail.

Java:

public static Node reverse(Node head){
	Node n = head, next;
	while(n.next() != null){
		next = n.next;
		n.next = n.prev;
		n.prev = next;
		n = next;
	}
	// n is the new head.
	return n;
}

Reversing doubly linked list is easier than SLL. Just reverse head and tail of each node of DLL.

reverseLinkedList(Node node)
{

if(node.nxt==null)
return;
else
{

reverseLinkedList(node.nxt)
Node tmp=node.prev;
node.prev=node.next;
node.next=tmp
}
---Ajeya

public static Node reverseLinkedListIteratively(Node head){
Node prev=null;
Node temp=head;
while(temp!=null){
Node temp1=temp.next;
temp.next=prev;
prev=temp;
temp=temp1;

}
return prev;
}

There are two ways to do the problem :
(1) to keep swapping the data of first and last node - O(n/2) - extra space not required
(2) to swap the next n prev pointers for each node. - O(n) - extra space required for swapping (= size of node)

Please feel free to comment and point out any possible mistake on above approches.

ListNode *reverse(ListNode* head)
	{
		if(head == NULL || head->next == NULL)
			return head;
		ListNode *p = head;
		while(p->next != NULL)
		{
			ListNode *temp = p->next;
			p->next = p->prev;
			p->prev = temp;
			p = temp;
		}
		p->next = p->prev;
		p->prev = NULL;
		return p;
	}

I think the emphasis on the question is more on "not use additional space", so all the algos using Next or any other temporary variable is not accepted.

In c++, all these pointers are anyways long, so you can do this to swap 2 pointers without using a temporary variable:

n1= (Node *) ((long)n1+ (long)n2);
n2 = (Node *) ((long)n1- (long)n2);
n1= (Node *) ((long)n1- (long)n2);

Find and return the tail, the list is reversed because it is a double linked list.

Use two pointers, p1 and p2. p1 move 1 step forward, p2 move 2 stop forward, when p2 return back to head, p1 will be the tail.

void reverse(node ** headRef)
{
        node* previousNode = NULL;
        node* curr = *headRef;
        while(curr)
        {
                curr->prev = curr->next;
                curr->next = previousNode;
                previousNode = curr;
                curr=curr->prev;
                if (curr == NULL)
                        {
                                *headRef = previousNode;
                                break;
                        }
        }
}

Most of you are not checking error conditions.
Try it with a list of length 1. Some of the above solutions I've seen will actually return null for the new head.

static DoublyLinkedNode reverse(DoublyLinkedNode head) {
		
		while (head.next != null) {
			DoublyLinkedNode tmpNext = head.prev;

			head.prev = head.next;
			head.next = tmpNext;
		
			head = head.prev;
		}
	
		head.next = head.prev;
		head.prev = null;
		
		return head;
	}

Why cant i swap just the data i the head and tail ??

do i really need to do all the pointer manipulations in a doubly linked list ??

Why cant i just swap the data elements present in the first and the last node ??

I know that people might think that what if the no of variables in the Node of the list is O(n). in that case it might not be a viable option to swap data.. but if the node has constant no of data variables then its better we just swap the data.

suggestions welcomed.

void reverse(){
node *temp=first,*temp2=first;
while(temp!=NULL){
swap(temp->next,temp->prev);
temp=temp->prev;}
swap(first,last);
}

void reverse(){
node *temp=first;
while(temp!=NULL){
swap(temp->next,temp->prev);
temp=temp->prev;}
swap(first,last);
}

void reverse(node **head,node **tail,int item)
{ node *loc;
item=*head->info;
while(*head->next!=null)
{
printf("%d",*head->info);
*head=*head->next;
*head->next=*head->next->pre;
}
loc=*head->next;
while(loc!=item)
{
printf("%d",loc->info);
loc->next=loc->pre;
}loc->pre=loc->pre->next;
loc->pre->next=null;
}

http://www.teamten.com/lawrence/writings/reverse_a_linked_list.html

C:

void reverse(node **head)
{
    node *prev = NULL;
    while (NULL != *head) {
        node *next = (*head)->next;
        (*head)->next = prev;
        prev = *head;
        *head = next;
    }
    *head = prev;
}

or:

void reverse(node **head)
{
    node *new_head = NULL;
    while (NULL != *head) {
        node *elem = *head;
        *head = (*head)->next;
        elem->next = new_head;
        new_head = elem;
    }
    *head = new_head;
}

Java:

public static Node reverse(Node head) {
    Node prev = null;
    while (head != null) {
        Node next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

or:

public static Node reverse(Node head) {
    Node newHead = null;
    while (head != null) {
        Node elem = head;
        head = head.next;
        elem.next = newHead;
        newHead = elem;
    }
    return newHead;
}

Note that above solutions can be easily transformed into recursive ones.

its a double linked list..so just swap the head and tail.