5

我必须在链表中交换两个相邻节点（不是它们的数据）。例如 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;
}
4

5 回答 5

3

看起来挺好的。我添加了一个正确性检查（第三个==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;
}
于 2013-01-10T19:47:37.173 回答
3

您可以通过递归相当简单地做到这一点：

// 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;
    }
}
于 2013-01-11T03:51:11.990 回答
2

你的算法是最好的。通常我们可以通过简单来获得一点速度。与其画图和推理指针，不如考虑从输入列表的头部弹出元素并使用队列添加到尾操作来构建结果。在伪代码中，我们有

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

if仅需要防止输入列表具有奇数长度的情况。如果我们确定列表长度相等，我们可以跳过它。

现在 pop 很容易实现。如果我们使用虚拟头节点，则添加尾操作是最简单的。所以在 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;
}

现在我还没有测试过这段代码，但我很确定它会以一个或两个错字为模运行良好。测试比你的少（每个元素只有一个）。测试相对昂贵，因为它们会干扰流水线，所以我的运行速度应该快一点。几乎可以肯定，这种差异是无关紧要的。

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

注意 现在我做了一个快速测试，第一次尝试就成功了！另一方面，当我尝试您的代码时，我得到了一个 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;
}
于 2013-01-11T03:00:14.270 回答
1

在 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);
}
于 2015-02-10T19:34:22.667 回答
0

Alex DiCarlo 的递归方法比较简单，但需要稍微修正一下。

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

如果我错了，请纠正我。

谢谢！

于 2014-10-22T23:29:31.323 回答