C++程序 将链表中的偶数节点和奇数节点分离

给定一个整数链表，编写一个函数来修改链接列表，使得所有偶数数字出现在修改的链接列表的所有奇数数字之前。同时，保持偶数和奇数数字的顺序不变。

举例：

输入： 17->15->8->12->10->5->4->1->7->6->NULL
输出： 8->12->10->4->6->17->15->5->1->7->NULL

输入： 8->12->10->5->4->1->6->NULL
输出： 8->12->10->4->6->5->1->NULL

//如果所有数字都是偶数则不更改列表
输入： 8->12->10->NULL
输出： 8->12->10->NULL

//如果所有数字都是奇数则不更改列表
输入： 1->3->5->7->NULL
输出： 1->3->5->7->NULL

方法1:

想法是得到指向链表尾节点的指针。然后从头节点开始遍历列表，并将奇数节点从其当前位置移动到列表的末尾。

算法：

• 获得指向最后一个节点的指针。
• 将所有奇数节点移动到末尾。
  • 在第一个偶数节点之前考虑所有奇数节点并将它们移动到末尾。
  • 将头指针更改为指向第一个偶数节点。
  • 在第一个偶数节点之后考虑所有奇数节点并将它们移动到末尾。

以下是上述方法的实现：

// C++程序，将链表中的偶数结点和奇数结点分离
#include <bits/stdc++.h>
using namespace std;
 
// 链表的结点
class Node
{
    public:
    int data;
    Node *next;
};
 
void segregateEvenOdd(Node **head_ref)
{
    Node *end = *head_ref;
    Node *prev = NULL;
    Node *curr = *head_ref;
 
    // 获取尾节点的指针
    while (end->next != NULL)
        end = end->next;
 
    Node *new_end = end;
 
    /*将第一个偶数结点之前的所有奇数结点移动到尾部*/
    while (curr->data % 2 != 0 &&
           curr != end)
    {
        new_end->next = curr;
        curr = curr->next;
        new_end->next->next = NULL;
        new_end = new_end->next;
    }
 
    // 10->8->17->17->15
    /*仅在有偶数节点时执行以下步骤*/
    if (curr->data%2 == 0)
    {
        /*改变头指针，使其指向第一个偶数节点*/
        *head_ref = curr;
 
        /*现在curr指向第一个偶数节点*/
        while (curr != end)
        {
            if ( (curr->data) % 2 == 0 )
            {
                prev = curr;
                curr = curr->next;
            }
            else
            {
                /*断开prev和curr之间的链接*/
                prev->next = curr->next;
 
                //将curr的下一个置为空
                curr->next = NULL;
 
                //移动curr到尾部
                new_end->next = curr;
 
                //将curr作为链表的新尾部
                new_end = curr;
 
                /*更新当前指针指向移动节点的下一个*/
                curr = prev->next;
            }
        }
    }
 
    /*这句话执行之前必须设置好prev*/
    else prev = curr;
 
    /*若有超过1个奇数节点且原链表尾结点是奇数则将这个节点移动到尾部以保持原链表中奇数数
    字的顺序不变*/
    if (new_end != end &&
       (end->data) % 2 != 0)
    {
        prev->next = end->next;
        end->next = NULL;
        new_end->next = end;
    }
    return;
}
 
// 实用方法
/*在链表开头插入一个节点的函数*/
void push(Node** head_ref,
          int new_data)
{
    //分配节点
    Node* new_node = new Node();
 
    //插入数据
    new_node->data = new_data;
 
    //将旧的链表连接到新节点上
    new_node->next = (*head_ref);
 
    //移动头指向新节点
    (*head_ref) = new_node;
}
 
// 打印链表中的节点
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data <<" ";
        node = node->next;
    }
}
 
// 驱动代码
int main()
{
    //头结点为空
    Node* head = NULL;
 
    /*创建一个样例链接列表
      0->2->4->6->8->10->11*/
    push(&head, 11);
    push(&head, 10);
    push(&head, 8);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);
    push(&head, 0);
 
    cout << "Original Linked list ";
    printList(head);
 
    segregateEvenOdd(&head);
 
    cout << "Modified Linked list ";
    printList(head);
 
    return 0;
}
//本代码的贡献者:rathbhupendra```  

输出

原链表 0 2 4 6 8 10 11 修改后的链表 0 2 4 6 8 10 11 

时间复杂度: O(n)

辅助空间: O(1)

方法二：

将链表分成两个部分：一个包含所有偶数节点，另一个包含所有奇数节点。最后，将奇数节点链表附加到偶数节点链表后面。

要分割链表，遍历原始链表，并将所有奇数节点移动到所有奇数节点的单独链表中。在循环结束时，原始列表将拥有所有偶数节点，而奇数节点列表将拥有所有奇数节点。为了保持所有节点的顺序相同，我们必须将所有奇数节点插入到奇数节点列表的末尾。为了在恒定时间内实现这一点，我们必须跟踪奇数节点列表中的最后一个指针。

// CPP程序，用于分离链表中的偶数和奇数节点
#include <stdio.h>
#include <stdlib.h>
 
//一个单向链表节点
struct Node
{
    int data;
    struct Node *next;
};
 
//分离偶数和奇数节点的函数。
void segregateEvenOdd(struct Node **head_ref)
{
    //链表中具有偶数值的起始节点。
    Node *evenStart = NULL;
     
    //具有偶数值列表的结束节点。
    Node *evenEnd = NULL;
     
    //具有奇数值列表的起始节点。
    Node *oddStart = NULL;
     
    //具有奇数值列表的结束节点。
    Node *oddEnd = NULL;
     
    //节点遍历列表。
    Node *currNode = *head_ref;
     
    while(currNode != NULL)
    {
        int val = currNode -> data;
         
        //如果当前值是偶数，则添加
        //到偶数值列表中。
        if(val % 2 == 0)
        {
            if(evenStart == NULL)
            {
                evenStart = currNode;
                evenEnd = evenStart;
            }
             
            else
            {
                evenEnd -> next = currNode;
                evenEnd = evenEnd -> next;
            }
        }
         
        //如果当前值为奇数，则添加
        //到奇数值列表中。
        else
        {
            if(oddStart == NULL)
            {
                oddStart = currNode;
                oddEnd = oddStart;
            }
            else
            {
                oddEnd -> next = currNode;
                oddEnd = oddEnd -> next;
            }
        }
                     
        //将头指针向前移动一步
        //方向
        currNode = currNode -> next;   
    }
     
    //如果奇数列表或偶数列表
    //为空，则不需要更改
    //因为所有元素是偶数
    //或者是奇数。
    if(oddStart == NULL ||
       evenStart == NULL)
    {
        return;
    }
     
    //在偶数列表之后添加奇数列表。    
    evenEnd -> next = oddStart;
    oddEnd -> next = NULL;
     
    //修改头指针，指向
    //偶数列表的开始。
    *head_ref = evenStart;
}
 
// 实用函数
/*在开头插入节点的函数*/
void push(struct Node** head_ref,
          int new_data)
{
    //分配节点
    struct Node* new_node =
           (struct Node*) malloc(sizeof(struct Node));
 
    //输入数据
    new_node->data = new_data;
 
    //将旧列表链接到
    //新节点
    new_node->next = (*head_ref);
 
    //将头部移动，指向
    //新节点
    (*head_ref) = new_node;
}
 
/*  在给定链表中打印节点*/
void printList(struct Node *node)
{
    while (node!=NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
// 驱动程序
int main()
{
    //从空列表开始
    struct Node* head = NULL;
 
    /*我们创建以下示例
       链表如下
       0-->1-->4-->6-->9-->10-->11 。*/
    push(&head, 11);
    push(&head, 10    push(&head, 9);
    push(&head, 6);
    push(&head, 4);
    push(&head, 1);
    push(&head, 0);
 
    printf("原始链表 ");
    printList(head);
 
    segregateEvenOdd(&head);
 
    printf("修改后的链表 ");
    printList(head);
 
    return 0;
}
//此代码由NIKHIL JINDAL贡献。```  

输出

原始链表 0 1 4 6 9 10 11 修改后的链表 0 4 6 10 1 9 11 

时间复杂度: O(n)

辅助空间 ：O(1)因为使用了常量空间