我试图在给定基于0的索引的情况下将单链表的两个节点交换到其中。在我的代码中，我处理了许多情况，但这种方法仅在j-i<=2时有效。如果i和j之间有3或更多的差异，我无法处理。
请帮助我纠正我的方法。
node* swap_nodes(node *head,int i,int j)
{
if(j<i)
{
int temp;
temp=i;
i=j;
j=temp;
}
node *prev1,*prev2,*temp1,*temp2;
if(i==j)
{
return head;
}
if(i==0 && abs(i-j)!=1)
{
int n=0;
node *temp=head;
prev1=head;
temp1=prev1->next;
while(n<j-1)
{
temp=temp->next;
n++;
}
prev2=temp;
temp2=prev2->next;
prev2->next=temp1;
temp1->next=prev1;
prev1->next=temp2->next;
temp2->next=prev2;
return temp2;
}
else if(abs(i-j)==1 && i!=0 )
{
int n=0;
node *temp=head;
while(n<i-1)
{
temp=temp->next;
n++;
}
prev1=temp;
temp1=prev1->next;
n=0;
while(n<j-i+1)
{
temp=temp->next;
n++;
}
temp2=temp;
prev1->next=temp2;
temp1->next=temp2->next;
temp2->next=temp1;
return head;
}
else if(i==0 && j==1)
{
temp1=head;
temp2=head->next;
node *temp3=temp2->next;
temp2->next=temp1;
temp1->next=temp3;
return temp2;
}
else
{
int n=0;
node *temp=head;
while(n<i-1)
{
temp=temp->next;
n++;
}
prev1=temp;
temp1=prev1->next;
n=0;
while(n<j-i)
{
temp=temp->next;
n++;
}
prev2=temp;
temp2=prev2->next;
prev1->next=temp2;
temp1->next=temp2->next;
temp2->next=prev2;
prev2->next=temp1;
return head;
}
}
交换链表中节点的指针竞争的基本原理很简单：
- 在列表中查找指向要交换的节点的指针。这些指针中的一个可以是
head指针，但至少有一个是列表中的某个next指针。请记住，这些指针指向要交换的节点 - 交换那些指针
- 交换这些节点的
next指针以恢复列表的剩余顺序 - 就是这样
要做到这一点，最简单的方法是使用指针到指针。这避免了必须完全携带prev指针，这使得算法比需要的复杂得可怕
你的方法很勇敢，但明显很复杂。坚持上面的算法，它会变得更清楚需要什么。找到一些指向你想要交换的东西的指针，交换它们，然后交换回它们的内部下一个指针。
考虑到所有这些，算法实现如下(保留只扫描列表一次以找到要交换的两个节点的愿望(。关于算法如何与代码匹配的评论是内联的：
node *swap_nodes(node *head, int i, int j)
{
if (i < 0 || j < 0 || i == j)
return head;
// order i and j
if (j < i)
std::swap(i,j);
// find the pointer pointing to i'th node.
node **pp1 = &head;
while (*pp1 && i-- > 0)
{
pp1 = &(*pp1)->next;
--j;
}
// finish finding the pointer pointing to the j'th node
node **pp2 = pp1;
while (*pp2 && j-- > 0)
pp2 = &(*pp2)->next;
// if either index was out of range, at least one of these will
// be null, and if that's the case, no swap will happen
if (*pp1 && *pp2)
{
// swap the pointers
std::swap(*pp1, *pp2);
// and swap *back* their next members
std::swap((*pp1)->next, (*pp2)->next);
}
return head;
}
示例
如果没有一个实际的例子，这是不公平的。下面将构建一个由十个元素组成的有序列表，编号为1..10。然后，它使用上面的基于零索引的交换例程来交换各种元素，特别是交换头节点、尾节点和一些内部节点的东西，然后通过反转交换来撤消所有这些，从而得到我们开始使用的列表。
#include <iostream>
struct node
{
int data;
struct node *next;
node(int x)
: data(x)
, next(nullptr)
{
}
};
void ll_print(node const *p)
{
while (p)
{
std::cout << p->data << ' ';
p = p->next;
}
std::cout << 'n';
}
void ll_free(node **head)
{
while (*head)
{
node *tmp = *head;
*head = tmp->next;
delete tmp;
}
}
node *swap_nodes(node *head, int i, int j)
{
if (i < 0 || j < 0 || i == j)
return head;
// order i and j
if (std::min(i,j) == j)
std::swap(i,j);
// find the pointer pointing to i'th node.
node **pp1 = &head;
while (*pp1 && i-- > 0)
{
pp1 = &(*pp1)->next;
--j;
}
// finish finding the pointer pointing to the j'th node
node **pp2 = pp1;
while (*pp2 && j-- > 0)
pp2 = &(*pp2)->next;
// if either index was out of range, at least one of these will
// be null, and if that's the case, no swap will happen
if (*pp1 && *pp2)
{
// swap the pointers
std::swap(*pp1, *pp2);
// and swap *back* their next members
std::swap((*pp1)->next, (*pp2)->next);
}
return head;
}
int main ()
{
// build a forward-chained linked list of ten items
node *head = NULL, **pp = &head;
for (int i=1; i<=10; ++i)
{
*pp = new node(i);
pp = &(*pp)->next;
}
// print the list
ll_print(head);
// swap the first and second nodes
printf("Swapping 0,1n");
head = swap_nodes(head, 0, 1);
ll_print(head);
// swap the first and last nodes
printf("Swapping 0,9n");
head = swap_nodes(head, 0, 9);
ll_print(head);
// swap two internal nodes
printf("Swapping 3,6n");
head = swap_nodes(head, 3, 6);
ll_print(head);
////////////////////////////////////////
// this shoudl swap everything back, so it should give us
// what we originally had.
// swap two internal nodes
printf("Swapping 3,6n");
head = swap_nodes(head, 3, 6);
ll_print(head);
// swap the first and last nodes
printf("Swapping 0,9n");
head = swap_nodes(head, 0, 9);
ll_print(head);
// swap the first and second nodes
printf("Swapping 0,1n");
head = swap_nodes(head, 0, 1);
ll_print(head);
// release the list
ll_free(&head);
}
输出
1 2 3 4 5 6 7 8 9 10
Swapping 0,1
2 1 3 4 5 6 7 8 9 10
Swapping 0,9
10 1 3 4 5 6 7 8 9 2
Swapping 3,6
10 1 3 7 5 6 4 8 9 2
Swapping 3,6
10 1 3 4 5 6 7 8 9 2
Swapping 0,9
2 1 3 4 5 6 7 8 9 10
Swapping 0,1
1 2 3 4 5 6 7 8 9 10
摘要
如果你记得你要做的事情：交换指针，而不是节点，那么你试图避免的大多数边缘情况都会消失。诀窍是找到指向要交换的节点的指针(而不是它们的值；实际的指针(，并交换这些指针的值
您正在使交换逻辑变得比需要的更复杂。请尝试以下操作：
node* get_node_at(node *head, int index, node **previous = nullptr)
{
if (previous) *previous = nullptr;
if ((!head) || (index < 0)) return nullptr;
node *temp = head;
while (index > 0)
{
if (!temp) return nullptr;
if (previous) *previous = temp;
temp = temp->next;
--index;
}
return temp;
}
void swap_nodes(node *&head, int i, int j)
{
if ((!head) || (i == j)) return;
node *previous_i, *previous_j;
node* temp_i = get_node_at(head, i, &previous_i);
node* temp_j = get_node_at(head, j, &previous_j);
if (!temp_i || !temp_j)
return;
if (previous_i)
previous_i->next = temp_j;
if (previous_j)
previous_j->next = temp_i;
node *temp = temp_i->next;
temp_i->next = temp_j->next;
temp_j->next = temp;
if (temp_i == head)
head = temp_j;
else if (temp_j == head)
head = temp_i;
}
实时演示
您似乎在努力处理角落案例，但您的代码仍然无法处理基本案例，这是因为您让它变得困难。试着再次分析它——任务是什么，实现任务的要求是什么。
让我来帮你：-
- 任务1-通过遍历链表找到第i个索引节点和第j个索引节点。(无需查找它们之间的距离(
- 任务2-交换两个节点
要求-要交换节点，请访问其上一个节点。(这对你来说似乎是已知的事情，因为你已经在代码中尝试过了(
一些角落案例-
- 如果i==j或i>j(由您的代码管理(
- 如果第i个节点没有以前的节点(即它是链表的头(
现在尝试分析您的代码。
如需参考，请参阅下方的代码
node *swap_nodes(node *head,int i,int j)
{
if(j<i)
{
int temp;
temp=i;
i=j;
j=temp;
}
node *prev1=NULL,*prev2=NULL,*temp1,*temp2;
node *swp;
int k=0;
if(i==j)
{
return head;
}
temp1=head;
while(k!=i)
{
prev1=temp1;
temp1=temp1->next;
k++;
}
prev2=prev1;
temp2=temp1;
while(k!=j)
{
prev2=temp2;
temp2=temp2->next;
k++;
}
// critical part
prev2->next = temp1;
swp = temp1->next;
temp1->next = temp2->next;
temp2->next = swp;
// check if prev1 exists
if(prev1)
prev1->next=temp2;
else
head=temp2;
return head;
}
希望这会有所帮助。
不断询问，不断增长：(