编写一个重新排列链表的函数，以将节点置于列表中奇数位置之后的偶数位置

问题描述

编写一个函数，该函数重新排列链表，以将节点置于列表中奇数位置之后的偶数位置，同时保留偶数和奇数的相对顺序.

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.

我在Sedgewick的《 C语言写的算法》一书中发现了这个问题.我尝试过但失败了.我试图将所有节点放在另一个链表上的偶数位置.非常感谢您的帮助.一个好主意就足够了.谢谢:).

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 :).

/*
 * 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;
}

推荐答案

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;
}

这篇关于编写一个重新排列链表的函数，以将节点置于列表中奇数位置之后的偶数位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！