Write a function that rearranges a linked list to put the nodes in even positions after the nodes in odd positions in the list

Question

Write a function that rearranges a linked list to put the nodes in even positions after the nodes in odd positions in the list, preserving the relative order of both the evens and the odds.

I found this problem in the book Algorithm in c writtern by Sedgewick. I have tried but failed. I trid to put all nodes in even positions on another linked list. It's grateful for you to help me. A good idea is enough. Thanks :).

This is my Code in C.

/*
 * File: rearranges.c <Exercise 3.36>
 * Note: Write a function that rearranges a linked list to put the nodes in even
 *       positions after the nodes in odd positions in the list, preserving the
 *       relative order of both the evens and the odds.
 *       NOTICE: I think it's necessary to use linked list with a dummy head.
 * Time: 2013-10-26 10:58
 */
#include <stdio.h>
#include <stdlib.h>

#define LEN 11

typedef struct node *link;
struct node {
    int  item;
    link next;
};

/* Traverse a linked list with a dummy head. */
void traverse(link t) {
    link x = t->next;

    while (x != NULL) {
        printf("%d ", x->item);
        x = x->next;
    }
    putchar('\n');
}

/* Detach even positon nodes from a linked list. */
link detach(link t) {
    link u = malloc(sizeof(*u));
    link x = t, y = u;

    /* x is odd position node. We should ensure that there's still one even
     * position node after x. */
    while (x != NULL && x->next != NULL) {
        y->next = x->next;
        x->next = x->next->next;
        x = x->next;
        y = y->next;
        y->next = NULL;
    }

    return u;
}

/* Combine two linked list */
link combine(link u, link t) {
    link x = u;
    link y = t->next;

    while (y != NULL) {
        link n = y->next;

        y->next = x->next;
        x->next = y;

        x = x->next->next;
        y = n;
    }

    return u;
}

/* The function exchanges the position of the nodes in the list. */
link rearranges(link t) {
    link u = detach(t);
    link v = combine(u, t);

    return v;
}

int main(int argc, char *argv[]) {
    int i;
    link t = malloc(sizeof(*t));
    link x = t;

    for (i = 0; i < LEN; i++) {
        x->next = malloc(sizeof(*x));
        x = x->next;
        x->item = i;
        x->next = NULL;
    }

    traverse(t);
    traverse(rearranges(t));

    return 0;
}

Answer 1

In the following, every time swap_nodes is called another odd sinks to the last sunk odd. The evens are grouped together on each iteration and they bubble up to the end of the list. Here is an example:

/*
[0]-1-2-3-4-5
1-[0-2]-3-4-5
1-3-[0-2-4]-5
1-3-5-[0-2-4]
*/

#include <stdio.h>
#include <stdlib.h>
#define LIST_LENGTH 10

struct node{
    int id;
    struct node *next;
};

void print_list(struct node *current)
{
    while(NULL != current){
        printf("node id = %d\n",current->id);
        current = current->next;
    }
    printf("Done\n");
}

struct node *swap_nodes(struct node *head_even, struct node *tail_even, struct node    *next_odd)
{
    tail_even->next = next_odd->next;
    next_odd->next = head_even;
    return next_odd;
}

struct node *reorder_list(struct node *head)
{
    struct node *head_even;
    struct node *tail_even;
    struct node *next_odd;
    struct node *last_odd;
    if(NULL == head->next){
        return head;
    }
    head_even = head;
    tail_even = head;
    next_odd = head->next;
    last_odd = head->next;
    head = swap_nodes(head_even, tail_even, next_odd);
    if(NULL != tail_even->next){
        tail_even = tail_even->next;
    }
    while (NULL != tail_even->next) {
        next_odd = tail_even->next;
        last_odd->next = swap_nodes(head_even, tail_even, next_odd);
        last_odd = last_odd->next;
        if(NULL != tail_even->next){
            tail_even = tail_even->next;
        }       
    }
    return head;    
} 

int main(void)
{
    int i;
    struct node *head = (struct node *) malloc(LIST_LENGTH*sizeof(struct node));
    struct node *mem = head;
    if(NULL == head){
        return -1;
    }
    struct node *current = head;
    for(i=0;i<LIST_LENGTH-1;i++){
        current->next = current + 1;
        current->id = i;
        current = current->next;
    }
    current->next = NULL;
    current->id = i;
    head = reorder_list(head);
    print_list(head);
    free(mem);  
    return 0;
}

Answer 2

#include <stdio.h>

struct list {
    struct list *next;
    int ch;
    };

void swap_odd_even (struct list **pp)
{
struct list *one, *two ;

for( ; (one = *pp) ; pp = &one->next) {
    two = one->next;
    if (!two) break;
    *pp = two;
    one->next = two->next;
    two->next = one;
    }
}

struct list arr[] =
{ {arr+1, 'A'} , {arr+2, 'B'} , {arr+3, 'C'} , {arr+4, 'D'}
, {arr+5, 'E'} , {arr+6, 'F'} , {arr+7, 'G'} , {arr+8, 'H'}
, {arr+9, 'I'} , {arr+10, 'J'} , {arr+11, 'K'} , {arr+12, 'L'}
, {arr+13, 'M'} , {arr+14, 'N'}, {arr+15, 'O'} , {arr+16, 'P'}
, {arr+17, 'Q'} , {arr+18, 'R'} , {arr+19, 'S'} , {arr+20, 'T'}
, {arr+21, 'U'} , {arr+22, 'V'}, {arr+23, 'W'} , {arr+24, 'X'}
, {arr+25, 'Y'} , {NULL, 'Z'} };
int main (void) {
    struct list *root , *ptr;

    root = arr;
    for (ptr=root ; ptr; ptr = ptr->next ) {
        printf( "-> %c" , ptr->ch );
        }
    printf( "\n" );

    printf( "Swap\n" );
    swap_odd_even ( &root);

    for (ptr=root ; ptr; ptr = ptr->next ) {
        printf( "-> %c" , ptr->ch );
        }
    printf( "\n" );

   return 0;
}

Answer 3

curr=head;
end=lastOfList;//last node if size of list is odd or last-1 node 

for(int i=1;i<=listSize()/2;i++)
{
     end->next=curr->next;
     end=end->next;
     end->next=null;
     if(curr->next!=null)
        if((curr->next)->next!=null)
           curr->next=(curr->next)->next;
    curr=curr->next;
}

Answer 4

You can implement a recursive solution where each call returns an updated node that will serve as the new next reference for the upper caller. We just have to go down the list until we find the last element, and then move every even node to the end of the list, and update the reference to the last element. Here's my solution (please try to do it yourself before looking at my and other solutions):

struct node {
    int val;
    struct node *next;
};

struct node *reorder_aux(struct node *l, int count, struct node **last);
struct node *reorder(struct node *l) {
    struct node *x;
    if (l == NULL)
        return NULL;
    return reorder_aux(l, 1, &x);
}

struct node *reorder_aux(struct node *l, int count, struct node **last) {
    struct node *n;
    if (l->next == NULL) {
        *last = l;
        return l;
    }
    n = reorder_aux(l->next, count+1, last);
    if (count & 1) {
        l->next = n;
        return l;
    }
    else {
        (*last)->next = l;
        l->next = NULL;
        *last = l;
        return n;
    }
}

At each step, if the current node l is an even node (as determined by count), then we append this node to the end, and tell the upper caller that its next pointer shall be updated to our next (because our next will be an odd node). In case we're an odd node, we just have to update our next pointer to whatever the recursive call returned (which will be a pointer to an odd node), and return the current node, since we will not move ourselves to the end of the list.

It's a nice exercise!