将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并保证奇数之间顺序不变，偶数之间顺序不变（创新工场）

84 阅读 0 评论 56 点赞

我是靠谱客的博主繁荣酸奶，最近开发中收集的这篇文章主要介绍将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并保证奇数之间顺序不变，偶数之间顺序不变（创新工场），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

示例：

交换前链表的顺序交换后链表的顺序

4→5→3→1→2 ==> 5→3→1→4→2

1 ==> 1 （链表仅含一个元素)

2→1 ==>1→2

==> (链表为空)

C/C++:

链表节点定义为：

struct node {

struct node *next;

int value;

};

struct node *swap(struct node *list);

注意点和要求如下:

1. swap函数要求对节点的指针/引用进行操作（不得创建任何新的链表节点）

2. 不得使用任何库函数/API，如需使用类似功能, 请自行实现

3. 不得将链表转化为其他类型数据结构再进行交换，如数组等

#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
    struct node *next;
    int value;
};
node* CreateListNode(int value)//链表中的节点建立
{
    if(value==NULL)
        return NULL;
    node* pNode = (node*)malloc(sizeof(node));
    pNode->value = value;
    pNode->next = NULL;
    return pNode;
}
void ConnectNodes(node* pCurrent, node* pNext)//连接2个结点
{
    if(pCurrent == NULL)
    {
        cout<<"Error to connect two nodes."<<endl;
        exit(1);
    }

    pCurrent->next = pNext;
}
void PrintList(node* pHead)//打印链表.
{
    node* pNode = pHead;
    while(pNode!=NULL)
    {
        cout<<pNode->value<<" ";
        pNode = pNode->next;
    }
    cout<<endl;
}
struct node *swap(struct node *list)
{
    if(list==NULL)
        return NULL;
    if(list->next==NULL)
        return list;
    node *p=list;
    node *OddHead=(node *)malloc(sizeof(node))
    node *EvenHead=(node *)malloc(sizeof(node));
    node *Odd=OddHead;
    node *Even=EvenHead;
    while(p)
    {
        if(p->value%2==1)//判断结点值是否为奇数
        {
            Even->next=p;
            Even=p;
        }
       else
       {
           Odd->next=p;
           Odd=p;
       }
       p=p->next;
    }
    Odd->next=NULL;//偶数链表最后一个结点值赋空.
    Even->next=OddHead->next;//奇数链表的最后一个值连接带头节点的偶数链表.
    return EvenHead->next;//返回不带头结点的链表
}

int main()
{
    //创建结点.
    node *pNode1=CreateListNode(4);
    node *pNode2=CreateListNode(5);
    node *pNode3=CreateListNode(3);
    node *pNode4=CreateListNode(1);
    node *pNode5=CreateListNode(2);
    //结点连接成链表.
    ConnectNodes(pNode1,pNode2);
    ConnectNodes(pNode2,pNode3);
    ConnectNodes(pNode3,pNode4);
    ConnectNodes(pNode4,pNode5);

    node *p=swap(pNode);
    PrintList(p);
}