Thursday, March 15, 2012

swap odd even position in linked list


#include <cassert>
#include <cstdio>
using namespace std;

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

node* swap(node *head)
{
    node dummy;
    node *prev, *curr, *u, *tmp;
    if (head==NULL) return head;

    prev=&dummy;
    for(curr=head; curr!=NULL && curr->next!=NULL; ) {
        u = curr->next;
        tmp = u->next;
        prev->next = u;
        u->next = curr;
        prev = curr;
        curr = tmp;
    }
    prev->next = curr;
    return dummy.next;
}

void print(const node *head)
{
    for(const node *p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}
int main()
{
    const int N=101;
    node v[N];
    
    for(int i=0; i<N; ++i) {
        v[i].val=10*i;
        if (i<N-1) v[i].next=&v[i+1];
        else v[i].next=0;
    }

    node *head=&v[0];
    puts("input");
    print(head);

    head = swap(head);
    puts("swap even odd");
    print(head);

}

No comments:

Post a Comment