c - 交换链表中的相邻元素

Question

在看一个编程面试网站时，我遇到了交换链表中相邻元素的代码，但我发现它有点不对。下面是代码。

void swap (struct list **list1)
{
    struct list *cur, *tmp, *next;
    cur = *list1;
    if (cur && cur->next)
        *list1 = cur->next;

    //To make sure that we have at least two more elements to be swapped.
    while (cur && cur->next)
    {
        next = cur->next;
        tmp = next->next;
        next->next = cur;
        //We have to make 1->next as 4 in above example (figure).

        if (tmp)
            cur->next = tmp->next;
        cur = tmp;
    }
    return;
}

现在对我来说，条件 if (temp) 不在这里。该评估是否正确？

假设我们有一个像这样的链表:

  1->2->3->4->NULL

现在我们的目标是创建一个链表，如下所示:

2->1->4->3->NULL

我担心的是，如果我们的代码中存在 if (temp)，我们就无法在链表末尾分配 null。

Answer 1

你是对的。这是行不通的。它会在列表末尾创建一个循环，如果您在同一个列表上运行 swap 两次，第二次运行将进入无限循环。

要修复这段笨拙的代码，请将 if (tmp) 替换为以下代码:

if(tmp)
    if (tmp->next)
        cur->next = tmp->next;
    else
        cur->next = tmp;    // take care of an add number of nodes
else
    cur->next = NULL;   // take care of an even number of nodes

它将处理最后的节点:

1. 如果有偶数个节点，它确保最后一个指向 NULL 而不是它之前的节点。
2. 如果有奇数个节点，检查 cur->next 将阻止后续迭代，因此在退出循环之前最后一个节点必须由前一个节点指向。