交换链表中相邻的元素

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将阻止后续迭代，因此在退出循环之前，最后一个节点必须由它之前的节点指向。

Answer 2

它测试它以确保它不是NULL(最后一个元素)。不测试它将使你的程序跟随列表最后一个元素的NULL指针。

tmp = next->next; /* If `next` is the last, `next->next` is NULL. */

Answer 3

是的，你是对的，在函数中有一个bug - cur->next在所有情况下都没有正确更新。

我个人认为局部变量名tmp和next不是特别有用，而且在next的情况下很容易混淆。这些名字使我在阅读函数时很难在脑海中跟踪发生了什么。

我发现名称node1, node2和node3对我来说更好地保持正在操作的节点的心理画面。但是，如果其他人不同意，我也不会感到惊讶。

下面是这个函数的修改版本，我觉得它更容易读懂，更重要的是，我认为它是正确的。

void swap (struct list **head)
{
    struct list *node1 = *head;
    struct list *node2 = node1 ? node1->next : NULL;
    // handle degenerate cases
    if (!node2) {
        // no elements or only one element on the list
        //  nothing to do...
        return;
    }    
    // fix-up list head to what will be the new first node on list
    *head = node2;        
    // while there are at least 2 more elements to be swapped
    while (node1 && node2) {
        struct list* node3 = node2->next;
        // get a pointer to the node that will be the remainder of the
        //  list after the remainder of the list is processed.  
        //
        // This will be NULL, node3, or 'node4' depending on whether 
        //  there are 0 , 1 or 2+ nodes following node1 and node2
        struct list* remainder = (node3 && node3->next) ? node3->next : node3;
        node1->next = remainder;
        node2->next = node1;
        // prepare pointers to the next two nodes to be swapped
        node1 = node3;
        node2 = node3 ? node3->next : NULL;
    }
    return;
}

Answer 4

Java实现

给定:1->2->3->4->5->6

逻辑1. 第一- 1，第二- 2，第三- 3
2. 第二。Next = first
3.第一。next =第三。下一步根据偶数或奇数相应地更新

public ListNode evenOddMerge(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = first.next;
        ListNode third = null;
        head = second;
        while (true) {
            third = second.next;
            second.next = first;
            if (third == null || third.next == null) {
                first.next = third;
                break;
            }
            first.next = third.next;
            first = third;
            second = first.next;
        }
        return head;
    }

credit: Geeks for Geeks