5

リンクされたリストで2つの隣接するノード(データではない)を交換する必要があります。例 1) 入力 a->b->c->d->e->f、出力: b->a->d->c->f->e 2) 入力 a->b->c- >d->e、出力: b->a->d->c->e

次のコードを書きましたが、より効率的な方法 (おそらく 2 つの一時ポインターを使用) または単純なロジックはありますか?

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

これは、再帰を使用してかなり簡単に行うことができます。

// 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 に答える
3

いいね。正確性チェック (3 番目の ==NULL) を 1 つ追加し、冗長な式を 1 つ削除しました。リスト全体を 1 回だけ確認する必要があります。したがって、これが最速の方法であると確信できると思います。

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 に答える
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;
}

今、私はこのコードをテストしていませんが、おそらくタイプミスか2つを法としてうまく実行されると確信しています。テストはあなたのテストよりも少なくなります（要素ごとに1つだけ）。テストはパイプラインに干渉する可能性があるため、比較的費用がかかるため、私の場合は少し速く実行する必要があります。ほぼ確実に、この違いは関係ありません。

ただし、私のコードは理解しやすいと思います。もちろん、それは偏った意見の1つにすぎませんが、読みやすさはメンテナンス中に重要です。

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;
}
于 2013-01-11T03:00:14.270 に答える
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 に答える