我正在尝试交换链表的相邻节点,即
1->2->3->4->5变成2->1->4->3->5
我的功能是:
node * swapper(node * &head)
{
if (head == NULL || head->next == NULL) return head;
node * t = head;
head= head->next;
head->next = t;
t->next = head->next;
node *previous = head->next->next, *current = previous->next;
while (current!=NULL&&previous!=NULL)
{
node * t1 = current,*t2=previous;
current->next = previous;
previous->next = t1->next;
previous = t1->next;
current = previous->next;
}
return head;
}
我知道它可以通过交换值来实现,但我必须在常量空间中进行操作,并且不能交换值。
我不知道为什么我的函数不工作
我注意到的第一件事是您需要交换这两行:
head->next = t;
t->next = head->next;
因为你说了head->next = t,所以你失去了与链表其余部分的连接。
同样,在循环内部。这里有几个错误:1-你在之前获得它之前改变了下一个电流,这意味着你失去了链接(如上所述)2-你没有将它们连接到它们之前的节点
我的五分钱。
下面是一个演示程序,演示如何编写递归函数。
#include <iostream>
#include <functional>
struct node
{
int data;
struct node *next;
} *head;
void push_front( node * &head, int x )
{
head = new node { x, head };
}
void display( node *head )
{
for ( node *current = head; current; current = current->next )
{
std::cout << current->data << ' ';
}
std::cout << std::endl;
}
node * swapper( node * &head )
{
if ( head && head->next )
{
node *tmp = std::exchange(head, head->next );
std::exchange( tmp->next, std::exchange( tmp->next->next, tmp ) );
swapper( head->next->next );
}
return head;
}
int main()
{
const int N = 10;
for ( int i = N; i != 0; ) push_front( head, --i );
display( head );
display( swapper( head ) );
}
程序输出如下
0 1 2 3 4 5 6 7 8 9
1 0 3 2 5 4 7 6 9 8
请注意并非所有编译器都支持函数std::exchange
。所以你需要自己写:)
如果按照下面的方式写main
int main()
{
const int N = 10;
for ( int i = N; i != 0; ) push_front( head, --i );
display( head );
for ( node **current = &head; *current && ( *current )->next; current = &( *current )->next )
{
swapper( *current );
}
display( head );
}
,则可以得到以下有趣的输出::)
0 1 2 3 4 5 6 7 8 9
1 3 5 7 9 8 6 4 2 0
node * swapper(node * &head)
{
if (head == NULL || head->next == NULL) return head;
node * t = head;
head= head->next;
t->next = head->next;
head->next = t;
node *previous = head->next->next, *current,*parent=head->next;
while (previous&&(current = previous->next))
{
node * t1 = current,*t2=previous;
previous->next = t1->next;
current->next = previous;
parent->next= current;
previous = t2->next;
//current = previous->next;
parent=t2;
}
return head;
}