问题是要求我们在链表中将奇数位置的元素放在偶数位置的元素之前。
测试用例：
{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;
}
此代码仅适用于链表中偶数个节点。如果我们在链表中取奇数个节点，那么它将显示分段错误。
例如：此代码将在第一个测试用例中正确工作。
但对于第二个测试用例，它将显示分段错误。
在进入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成为一个问题并引发分割故障。你可以把那部分整体去掉。
不相关，但看看为什么我不应该#include<bits/stdc++.h>？。
这看起来像是一个家庭作业问题，所以我不想给出确切的答案。在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
这可能是一个很大的学习曲线，但要将代码放在VisualStudio测试库类的顶部，或者将源文件重写为Googletest文件。这样，您就可以执行您在问题中确定的两种测试模式。还有：
- 如果列表中包含奇数个项目，会发生什么
- 如果它是一个空列表怎么办
从那里，您可以轻松地添加更多的测试用例并重新测试您的代码。
我的五美分。：(
对于初学者来说，不需要显式声明类节点的构造函数。
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
这并不能回答您的问题，因为它没有解释您的尝试有什么问题。如果有人回答这个问题，那将是一个更好的答案。
然而，这个答案更多的是为了让你了解如何使用标准C++库算法来解决它，这对你来说是可用的，使用它并不可耻。
#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, " "));
}
当列表中的元素数量为奇数时，偶数指针指向NULL，因此在while条件下无法访问偶数的下一个节点。请尝试以下代码，它将解决您的问题。
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* next;
node(int val){
data = val;
next = NULL;
}
};
void insertAtTail(node* &head,int val){
node* n = new node(val);
if(head == NULL){
head = n;
return;
}
node* temp = head;
while(temp->next!=NULL){
temp=temp->next;
}
temp->next = n;
return;
}
void display(node* &head){
node* temp = head;
while(temp!=NULL){
cout<<temp->data;
if(temp->next!=NULL){
cout<<"->";
}
temp = temp->next;
}
cout<<endl;
return;
}
void evenAfterOdd(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;
if(even->next!=NULL){
even = even->next;
}else{
break;
}
}
odd->next = evenStart;
return;
}
int main(){
node* head = NULL;
int arr[] = {1,2,3,4,5,6,7};
for(int i=0;i<6;i++){
insertAtTail(head,arr[i]);
}
display(head);
evenAfterOdd(head);
display(head);
return 0;
}
希望你觉得它有帮助！：(
不是回答您的问题，而是建议一种更简单的方法来解决问题。
您还可以在链接列表上向后循环，并将所有奇数移动到列表的开头。
它看起来像这样：
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;
}