在C ++中的链表中分隔偶数和奇数节点 [英] Segregate even and odd nodes in a Linked List in C++

问题描述

因此，我正在自学数据结构和算法.在解决一些问题时，我遇到了以下问题，我必须隔离链表的奇数和偶数节点.

So, I am self teaching Data Structure and Algorithm. While solving some problems I came across following problem where I have to segregate odd and even nodes of linked list.

http://www.geeksforgeeks.org/segregate-even-and-odd-elements-in-a-linked-list/

以下是问题说明:

给出一个整数链接列表，编写一个函数来修改链接列表，以使所有偶数出现在修改后的链接列表中的所有奇数之前.另外，还要保持偶数和奇数的顺序相同.

Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.

我知道这个问题被问了很多遍了.但是我仍然找不到答案.我知道有多种方法可以解决此问题，但尝试以以下方式解决

I know this question is asked so many times. But I am still not able to find the answer. I know there are multiple ways to solve this problem but trying to solve this in following way

    1. Traversing over the original list and moving all the odd elements to new oddlist. 
       Same time delete those elements from the original list.
    2. Now original list should have even elements and oddlist will have odd elements.
    3. concatenate original list and oddlist 

哪个看起来直截了当我以为只删除节点并调整几个指针就可以解决问题，但事实并非如此

Which looks straight forward and I thought just by removing node and adjusting few pointer would solve the problem but it is not the case

#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node {
    int data;
    struct Node *next;
};


struct Node *Insert_at_bottom(struct Node* head, int data) {
    struct Node *node;

    node = new struct Node;
    node->data = data;
    node->next = NULL;
    //node->prev = NULL;

    struct Node *temp;

    if (head == NULL) {
        head = node;
        return head;
    }

    temp = head;
    while(temp->next != NULL){
        temp = temp->next;
    }

    temp->next = node;
    //node->prev = temp;
    return head;
}




struct Node *seperate_elements(struct Node *head) {
    struct Node *temp = head;
    struct Node *oddhead = NULL;
    struct Node *temp1 = NULL;
    while (temp != NULL) {
        if (temp->data%2 == 0) {
            cout << "even:" << temp->data << "\n";


        }
        else{
            cout << "odd:" << temp->data << "\n";
            oddhead = Insert_at_bottom(oddhead, temp->data);

            // I am messing something here. Not sure what!!!
            temp1 = temp->next;
            temp->next = temp1->next;
            //temp->next = temp->next->next;
            free(temp1);
        }

        temp = temp->next;
    }
    return oddhead;
}

struct Node *concate_list(struct Node *head, struct Node *oddhead) {
    struct Node *temp = head;
    while(head->next!=NULL)
    {
        head = head->next;
    }
    head->next = oddhead;
    return temp;

}

void print_list(struct Node *head){
    while(head){
        cout << head->data << " ";
        head = head->next;
    }
}

int main(){

    struct Node *head = NULL;
    struct Node *head2 = NULL;
    struct Node *finalhead = NULL;
    head = Insert_at_bottom(head, 1);
    head = Insert_at_bottom(head, 2);
    head = Insert_at_bottom(head, 8);
    head = Insert_at_bottom(head, 4);
    head = Insert_at_bottom(head, 5);
    head = Insert_at_bottom(head, 7);

    head2 = seperate_elements(head);


    finalhead = concate_list(head, head2);
    //cout << "\n";
    print_list(finalhead);

    return 0;
}

所以当我执行上面的代码时，我得到了

so when I execute above code I am getting

1 8 4 5 1 5 instead of 2 8 4 1 5 7

现在，我认为删除节点时缺少某些内容.不知道我在这里做错了什么.我认为我没有适当地注意指针调整.非常感谢您的帮助.

Now, I think I am missing something while deleting the node. Not sure what I am doing wrong here. I think I am not taking proper care of pointer adjustment. I would really appreciate any help here.

谢谢

推荐答案

如果您不想创建第二个列表(这并不是真正必要的)，则最好的方法是使用如下算法:

If you don't want to create a second list, which is not really necessary, the best thing you can do is an algorithm like this:

1)找到列表的最后一个元素(您可以在线性时间内完成此操作)

1) find the last element of the list (you can do that in linear time)

2)开始遍历列表，每次找到奇数元素时，都将其放在列表的末尾.很容易，您只需要调整前一个元素，后一个元素，奇数元素本身和最后一个元素的指针即可.

2) start traversing the list, each time you find an odd element, you put it at the end of the list. It is easy, you just need to adjust the pointers of the preceding element, the following element, the odd element itself and of the last element.

执行#2，直到找不到列表的最后一个元素.为此，您必须为最后一个元素保存两个指针，一个指针将在您将奇数元素放在最后一个时进行更新，另一个将仅标记您原始列表的结尾，从而允许您终止算法.

Do #2 till you don't find the last element of the list. To keep track of this you will have to save two pointers for the last element, one that you will update as you put odd elements in the last and the other that will just mark you the ending of the original list, allowing you to terminate the algorithm.

这篇关于在C ++中的链表中分隔偶数和奇数节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！