在链表中奇数位置的元素之后放置偶数位置的元素

Question

题目要求我们在链表中将奇数位置的元素放在偶数位置的元素之前。

测试用例：

{1, 2, 3, 4, 5, 6} --> {1, 3, 5, 2, 4, 6}

{1, 2, 3, 4, 5, 6, 7} --> {1, 3, 5, 7, 2, 4, 6}

我的代码：

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
    int data;
    node *next;

    node(int value)
    {
        data = value;
        next = NULL;
    }
};

void InsertAtHead(node *&head, int val)
{
    node *n = new node(val);

    n->next = head;
    head = n;
}

void InsertAtTail(node *&head, int val)
{
    if (head == NULL)
    {
        InsertAtHead(head, val);
        return;
    }
    node *n = new node(val);

    node *temp = head;

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

void EvenOdd(node *&head)
{
    node *odd = head;
    node *even = head->next;
    node *evenStart = even;

    while (odd->next != NULL && even->next != NULL)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    if (odd->next == NULL)
    {
        even->next = NULL;
    }
    odd->next = evenStart;
}

void display(node *head)
{
    node *temp = head;

    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main()
{
    node *head = NULL;

    int a[] = {1, 2, 3, 4, 5, 6, 7};

    for (int i = 0; i < 7; i++)
    {
        InsertAtTail(head, a[i]);
    }
    display(head);

    EvenOdd(head);
    display(head);

    return 0;
}

此代码仅适用于链表中偶数个节点。如果我们在链表中取奇数个节点，那么它将显示分段错误。

例如：此代码将对第一个测试用例正常工作。

但是对于第二个测试用例，它会显示分段错误。

Answer 1

在进入 OddEven 循环之前，odd 是 1，even 是 2。

    while (odd->next != NULL && even->next != NULL)
    {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }

第一次循环后，odd为3，even为4。接下来是odd为5，even为6，则odd为7 和 even 是 NULL.

    if (odd->next == NULL)
    {
        even->next = NULL;
    }

由于 even 是 NULL，even->next 成为一个问题并抛出分段错误。您可以将那部分整体删除。

不相关，但请看一下。

Answer 2

这并没有回答你的问题，因为它没有解释你的尝试有什么问题。如果有人回答这个问题，那将是一个更好的答案。

然而，这个答案更多的是供您参考如何使用标准 C++ 库 algorithms 来解决这个问题，您可以使用它，而且使用起来并不丢人。

#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7};

    // a lambda function that tests whether a single number is odd
    auto is_odd = [](int i){ return i % 2 > 0; };

    // reorganise elements such that odd numbers are moved to the front, maintaining their original order (stable)
    std::stable_partition(v.begin(), v.end(), is_odd);

    // output elements (space delimited) to console 
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Answer 3

这看起来像是一道作业题，所以我不想给出确切的答案。您在 EvenOdd() 函数中正朝着正确的方向前进：

node *odd = head;
node *even = head->next;
node *evenStart = even;

但是，开始于：

node *odd = nullptr;
node *even = nullptr;
node *current = head;

while (current != nullptr)
{
    // partition into odd and even sets here

    current = current->next;
}

// put the first even-node pointer at the end of the odd partition

这可能是一个很大的学习曲线，但将您的代码放在 Visual Studio 测试库的顶部 class 或将源文件重写为 Googletest 文件。这样，您就可以执行您在问题中确定的两种测试模式。还有：

如果列表包含奇数项会怎样？
如果是空列表怎么办？

从那里，您可以轻松添加更多测试用例并重新测试您的代码。

Answer 4

不是在回答你的问题，而是建议一个更简单的解决问题的方法。

您也可以在链表上向后循环并将所有奇数移动到链表的开头。

看起来像这样：

int main()
{
    node *head = NULL;

    int a[] = {1, 2, 3, 4, 5, 6, 7};

    for (int i = 7; i > 0; i--)
    {
        if(value == odd) {
            move to front of the list
    }

    return 0;
}

Answer 5

我的五分钱。:)

对于初学者来说，没有必要为 class 节点显式声明构造函数。

class node
{
public:
    int data;
    node *next;

    node(int value)
    {
        data = value;
        next = NULL;
    }
};

如果你处理聚合，你的生活会更简单。例如

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

函数名称 EvenOdd 令人困惑，因为从您的示例中可以看出，您希望重新排列列表，使奇数位置的节点先于偶数位置的节点，并且您从 1 开始计算位置。所以函数名至少要OddEven。否则，如果从 0 开始定位，那么函数名确实应该是 EvenOdd.

该函数最初可以调用未定义的行为，因为没有检查 head 是否等于 nullptr。因此，例如在这些语句中可以使用空指针来访问内存

node *even = head->next;

和

while (odd->next != NULL && even->next != NULL)

此外，列表不必包含奇数和偶数交替的节点序列。例如，尝试运行您的函数以获得包含以下数字序列 { 1, 3, 2, 4, 5 }.

的列表

我会这样写程序

#include <iostream>
#include <functional>
#include <iterator>

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

void push_front( node * &head, int data  )
{
    head = new node { data, head };
}

void clear( node * &head )
{
    while ( head ) delete std::exchange( head, head->next );
}

std::ostream & display( node * &head, std::ostream &os = std::cout )
{
    for ( const node *current = head; current; current = current->next )
    {
        os << current->data << ' ';
    }
    
    return os;
}

template <typename InputIterator>
void create( node * &head, InputIterator first, InputIterator last )
{
    clear( head );
    
    node **current = &head;
    
    for ( ; first != last; ++first )
    {
        *current = new node { *first, nullptr };
        current = &( *current )->next;
    }
}

node * EvenOdd( node * &head )
{
    node **odd = &head;
    node *even_head = nullptr;
    node **even = &even_head;
    
    size_t pos = 0;
    
    while ( *odd )
    {
        if ( pos++ % 2 != 0 )
        {
            *even = *odd;
            *odd = ( *odd )->next;
            ( *even )->next = nullptr;
            even = &( *even )->next;
        }
        else
        {
            odd = &( *odd )->next;
        }
    }
    
    *odd = even_head;
    
    return even_head;
}

int main() 
{
    node *head = nullptr;
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    create( head, std::begin( a ), std::end( a ) );
    
    display( head ) << '\n';
    
    auto pos = EvenOdd( head );
    
    display( head ) << '\n';
    display( pos ) << '\n';
    
    clear( head );
    
    return 0;
}

程序输出为

0 1 2 3 4 5 6 7 8 9 
0 2 4 6 8 1 3 5 7 9 
1 3 5 7 9

在链表中奇数位置的元素之后放置偶数位置的元素

Put elements at Even position after elements at Odd position in a Linked List

c++

partitioning

linked-list

singly-linked-list

function-definition