Reverse alternate elements and append to end of the list

Question

Given a linked list as a->x->b->y->c->z , we need to reverse alternate element and append to end of list. That is , output it as a->b->c->z->y->x.

I have an O(n) solution but it takes extra memory , we take 2 lists and fill it with alternate elements respectively , so the two lists are a b c and x y z and then we will reverse the second list and append it to the tail of first so that it becomes a b c z y x .

My question is can we do it in place ? Or is there any other algorithm for the same ?

Answer 1

The basic idea:

Store x.
Make a point to b.
Make y point to the stored element (x).
Make b point to c.
etc.
At the end, make the last element at an odd position point to the stored element.

Pseudo-code: (simplified end-of-list check for readability)

current = startOfList
stored = NULL
while !endOfList
  temp = current.next
  current.next = current.next.next
  temp.next = stored
  stored = temp
  current = current.next
current.next = stored

Complexity:

O(n) time, O(1) space.

Answer 2

Here is logic in recursion mode

public static Node alRev(Node head)
{
    if (head == null) return head;      
    if (head.next != null) 
    {
        if (head.next.next != null) 
        {
            Node n = head.next;
            head.next = head.next.next;
            n.next = null;
            Node temp = alRev(head.next);
            if (temp != null){
                temp.next = n;
                return n;
            }           
        }
        else
            return head.next;
    } 
    else
         return head;
    return null;
}

Answer 3

This is a recent question from amazon interview, the Idea looks good and there seems to be no trick in it.

Answer 4

Java code with comments:

static void change(Node n)
{
    if(n == null)
            return;

    Node current = n;

    Node next = null, prev = null;

    while(current != null && current.next != null)
    {
        // One of the alternate node which is to be reversed.
        Node temp = current.next;

        current.next = temp.next;

        // Reverse the alternate node by changing its next pointer.
        temp.next = next;

        next = temp;

        // This node will be used in the final step
       // outside the loop to attach reversed nodes.
        prev = current;

        current = current.next;            
    }

     // If there are odd number of nodes in the linked list.
     if(current != null)
       prev = current;

     // Attach the reversed list to the unreversed list.   
     prev.next = next;

}

Answer 5

here the c code which don't uses any extra space for doing this..enjoy and have fun in case of any doubt feel free to ask

    #include<stdio.h>
    #include<stdlib.h>

    int n;
    struct link

    {
    int val;
    struct link *next; 
    };



 void show(struct link *);

 void addatbeg(struct link **p,int num)
 {
 struct link *temp,*help;
 help=*p;
 temp=(struct link *)malloc(sizeof(struct link));
 temp->val=num;
 temp->next=NULL;
   if(help==NULL)
   {
   *p=temp;
   }
   else
   {
    temp->next=help;
    *p=temp;
   }
   n++;
 show(*p);
 }

 void revapp(struct link **p)
 {
 struct link *temp,*help,*q,*r;
 r=NULL;
 temp=*p;
 help=*p;

 while(temp->next!=NULL)
 {

    temp=temp->next;
    q=r;                     //this portion will revrse the even position numbers 
    r=temp;

    temp=temp->next;

    //for making a connection between odd place numbers
    if(help->next->next!=NULL)
    {
    help->next=temp;
    help=help->next;
    r->next=q;

    }

    else
    {
        r->next=q;
        help->next=r;
        show(*p);  
     return;
    }
 }

 }

 void show(struct link *q)
 {
    struct link *temp=q;
   printf("\t");
   while(q!=NULL )
   {

   printf("%d ->",q->val);
   q=q->next;
   if(q==temp)
   {
    printf("NULL\n");
    return;
   }
   }
   printf("NULL\n");
 }

 int main()
 {
 n=0;
 struct link *p;
 p=NULL;

 // you can take user defined input but here i am solving it on predefined list
 addatbeg(&p,8);
 addatbeg(&p,7);
 addatbeg(&p,6);

 addatbeg(&p,5);
 addatbeg(&p,4);

 addatbeg(&p,3);
 addatbeg(&p,2);
 addatbeg(&p,1);


 revapp(&p);

 return 0;
 }`