交换链表中相邻节点

Question

我需要在一个链表中交换两个相邻的节点（不是它们的数据）。 例如： 1) 输入a->b->c->d->e->f，输出：b->a->d->c->f->e 2) 输入a->b->c->d->e，输出：b->a->d->c->e 我已经编写了以下代码，还有更有效的方法（也许使用两个临时指针）或简单的逻辑吗？

node* swap(node* head) {
   node *first = head;
   node *second,*third,*result;

   if(head == NULL || head->next == NULL) {
        return head;
   }

    result = second = first->next;
    third = second->next;

    while(second != NULL) {
       second->next=first;
       first->next=(third->next==NULL ? third : third->next);
       first=third;
       second=(third->next==NULL ? third : third->next);
       third=(second==NULL ? second : second->next);
    }
    return result;
}

- Vallabh Patade

Answer 1

看起来很不错。我添加了一个正确性检查（third==NULL），并删除了一个多余的表达式。你只需遍历整个列表一次即可完成，这是必须做的。因此，我认为我们可以相当确定这是最快的方法。

node* swap(node* head) {
   node *first = head;
   node *second,*third,*result;

   if(head == NULL || head->next == NULL) {
        return head;
   }

    result = second = first->next;
    third = second->next;

    while(second != NULL) {
       second->next=first;
       second = first->next=((third==NULL || third->next==NULL) ? third : third->next);
       first=third;
       third=(second==NULL ? second : second->next);
    }
    return result;
}

- Spundun

---

我不确定是否真的需要这个（third==NULL）？是的，这是多余的表达。 :-) - Vallabh Patade

假设列表为A->B。初始时，first =＆A，second =＆B，third = NULL。然后当您尝试评估third->next时，会出现段错误。通过添加third == NULL条件，您可以避免段错误。 - Spundun

Answer 2

你可以通过递归相对简单地实现这一点：

// Swaps node b and c.
void swapTwo(node* a, node* b, node* c) {
   if (a != NULL)
       a->next = c;
   b->next = c->next;
   c->next = b;
}

void swapEveryTwo(node* prev, node* node) {
    if (node != null && node->next != null) {
        swapTwo(prev, node, node->next);
        swapEveryTwo(node->next, node->next->next);
    }
}

每次调用swapEveryTwo函数都会交换一对节点，然后为下一对节点设置递归。由于此函数是尾递归的，编译器无疑会将其优化为while循环，确保不会分配额外的堆栈帧，因此将是最佳选择。如果需要进一步解释，请随时提问。

编辑添加swap函数，与原帖相同：

node* swap(node *head) {
    if (head != NULL && head->next != NULL) {
        node *newHead = head->next;
        swapEveryTwo(NULL, head);
        return newHead;
    } else {
        return head;
    }
}

- Alex DiCarlo

Answer 3

您的算法是最佳的。通常，我们可以通过简单性获得一些速度。不要绘制图片或考虑指针，而是考虑从输入列表的头部弹出元素并使用队列添加到尾部操作来构建结果。伪代码如下：

set_empty(rtn);
while (head) {
   fst = pop(head);
   if (head) {
     snd = pop(head);
     add_at_tail(rtn, snd);
   }
   add_at_tail(rtn, fst);
}

if语句只需要用来保护输入列表长度为奇数的情况。如果我们确定列表长度为偶数，可以跳过它。

现在，弹出操作非常容易实现。如果我们使用一个虚拟头结点，添加到尾部的操作就最简单了。因此，在C语言中，我们有：

node *swap(node *head)
{
  node dummy[1];         // set_empty(rtn);
  node *rtn = dummy;
  while (head) {
    node *fst = head;    // fst = pop(head);
    head = head->next;
    if (head) {
      node *snd = head;  // snd = pop(head);
      head = head->next;
      rtn->next = snd;   // add_to_tail(rtn, snd);
      rtn = rtn->next;
    }
    rtn->next = fst;     // add_to_tail(rtn, fst);
    rtn = rtn->next;
  }
  rtn->next = NULL;      // terminate tail
  return dummy->next;
}

现在我还没有测试过这段代码，但我相信它会正常运行，除非有一两个笔误。与你的测试相比，我的测试要少一些（每个元素只有一个测试）。测试相对昂贵，因为它们可能会干扰流水线，所以我的代码应该会稍微快一点。几乎肯定这种差异是无关紧要的。

然而，我认为我的代码更容易理解。当然，这只是一个有偏见的观点，但可维护性确实很重要。

NB 现在我已经进行了快速测试，并且第一次尝试就成功了！另一方面，当我尝试你的代码时，我在...处遇到了segv错误。

 first->next=(third->next==NULL ? third : third->next);

以下是测试框架。你看到有什么问题吗？

typedef struct node_s {
  struct node_s *next;
  int val;
} node;

// swap goes here

int main(void)
{
  node dummy[1];
  node *p = dummy;

  for (int i = 0; i < 16; i++) {
    p->next = malloc(sizeof(node));
    p = p->next;
    p->next = NULL;
    p->val = 'a' + i;
  }
  p = swap(dummy->next);
  while (p) {
    printf("%c ", p->val);
    p = p->next;
  }
  printf("\n");
  return 0;
}

- Gene

Answer 4

在JavaScript中

LinkedList.prototype.swapPairs = function() {
    var recurse = function(current) {
        if (!current) return this;
        if (current.next) {
            var save = current.next.value;
            current.next.value = current.value;
            current.value = save;
            current = current.next;
        }
        return recurse(current.next);
    }.bind(this);
    return recurse(this.head);
}

- Alex Hawkins

Answer 5

Alex DiCarlo的递归方法更简单，但需要稍作修改。

void swapEveryTwo(node* prev, node* node) {
    if (node != null && node->next != null) {
        swapTwo(prev, node, node->next);
        swapEveryTwo(node, node->next);
    }
}

如果我错了，请纠正我。

谢谢！

- Frank