C - 単一リンクリストの最初と最後の要素を交換する

Question

私がしようとしているのは、単独リンクリストの最初と最後の要素を入れ替えることです。これまでのところ、私はリストを作成し、そこにいくつかの数字を追加する次のコードを持っています。私の問題は、swapElements1関数です。

#include <stdio.h> 
#include<stdlib.h> 

struct node 
{ 
    int number; 
    struct node *next; 
}; 

void addNodeSingle(struct node **head, int num, int thesi) //Function to insert new node at the beginning or the end of the list, depending on the value of "thesi" 
{ 
    if (*head == NULL) 
    { 
     struct node *current; 
     current = (struct node*) malloc (1*sizeof(struct node)); 
     current -> number = num; 
     current -> next = NULL; 
     *head = current; 
    } 

    else 
    { 
     if (thesi == 0) 
     { 
      struct node *current; 
      current = (struct node*) malloc (1*sizeof(struct node)); 
      current -> number = num; 
      current -> next = *head; 
      *head = current; 
     } 

     else 
     { 
      struct node *current, *temp; 
      current = (struct node*) malloc (1*sizeof(struct node)); 
      current -> number = num; 
      temp = *head; 
      while (temp -> next != NULL) 
       temp = temp -> next; 

      temp -> next = current; 
      current -> next = NULL; 
     } 
    } 
} 

void displayList(struct node **head) //Function to display the list 
{ 
    struct node *current; 
    if(*head == NULL) 
     printf("I lista einai adeia!\n"); 

    else 
    { 
    current= *head ; 
     while(current != NULL) 
     { 
      printf("%d ",current -> number); 
      current = current -> next; 
     } 
    } 
} 

void swapElements1(struct node **head) //(not working)Function to swap first and last element of the list 
{ 
    struct node *current, *temp; 
    current = temp = *head; 

    while(current != NULL) 
    { 
     temp = current; 
     current = current -> next; 
    } 

    *head = (*head)->next; 
    *head = temp; 
    current = NULL; 
} 

int main() 
{ 
    struct node *head; 
    head = NULL; 

    addNodeSingle(&head,5,1); 
    addNodeSingle(&head,6,1); 
    addNodeSingle(&head,2,0); 
    addNodeSingle(&head,7,0); 
    addNodeSingle(&head,8,0); 

    printf("List is: "); 
    displayList(&head); 
    swapElements1(&head); 
    printf("\nNew list is: "); 
    displayList(&head); 
} 

私が手出力は次のようになります。

一覧は以下のとおりです。8 7 2 5 6

新しいリストがある：6

iが必要なもの：

一覧は以下のとおりです。 8 7 2 5 6

新しいリストは：6 7 2 5 8

は、ここでこれは明らかに間違っているdemo

Answer 1

です：ちょうどtempの値と前の値を上書き

*head = (*head)->next; 
*head = temp; 

を。最初の声明はそこにさえあるかもしれません。

あなたは基本的に2つのスワップ（割り当ておよび終了プラス技術1）は、2つのノード

つのノードこれらのISNのnextポインタ

後者を指し

• ポインタを必要とします技術的には必要ありませんが、直接割り当てはで、新しいテールにはnextを設定して新しいリストを終了する必要があります。

  完全な例を以下に示しますが、何が起きているのかのアルゴリズムを公開したいと願っています。

  #include <stdio.h> 
  #include <stdlib.h> 
  
  struct node 
  { 
      int data; 
      struct node *next; 
  }; 
  
  void swapFirstAndLast(struct node **head) 
  { 
      // don't bother unless we have a list of at least two nodes 
      if (!*head || !(*head)->next) 
       return; 
  
      // start with the head's next pointer (the second node in the list) 
      struct node **pp = &(*head)->next; 
  
      // walk the pointer-to-pointer down the list, each time grasping 
      // the next node's "next" pointer address until we reach a node 
      // whose 'next' is NULL. When that happens, `pp` will hold the 
      // address of the pointer pointing to the last node in the list 
      while (*pp && (*pp)->next) 
       pp = &(*pp)->next; 
  
      // swap the pointer held in *head with *pp 
      struct node *tmp = *head; 
      *head = *pp; 
      *pp = tmp; 
  
      // save new head's next pointer to be the old head's next 
      (*head)->next = (*pp)->next; 
  
      // and finally, terminate the list. 
      (*pp)->next = NULL; 
  } 
  
  void print_list(const struct node *head) 
  { 
      while (head) 
      { 
       printf("%d ", head->data); 
       head = head->next; 
      } 
      fputc('\n', stdout); 
  } 
  
  int main() 
  { 
      struct node *head = NULL, **pp = &head; 
      for (int i=1; i<=5; ++i) 
      { 
       *pp = malloc(sizeof **pp); 
       (*pp)->data = i; 
       pp = &(*pp)->next; 
      } 
      *pp = NULL; 
  
      print_list(head); 
  
      swapFirstAndLast(&head); 
  
      print_list(head); 
  } 
  

  出力

  1 2 3 4 5 
  5 2 3 4 1 
  

  私はあなたのためのリストのクリーンアップ（すでにコード化されたこのようなアルゴリズムを持っている疑いを）残してきました。これの要点は、リンクされたリストのポインタを操作するポインタへのポインタの使用方法です。一時的なポインタの束だけではありません。私は、デバッガの交換機能を一歩一歩進んで、各ステップで何が起きているのかを見ておくことを強くお勧めします。

Answer 2

WhozCraigの回答は既に完璧ですが、おそらく自分のコードをいくつかの調整で見たいかもしれません。基本的に、私がやったのは、前回の最後の要素の探索を早く止めて、一時は5時に、現在は6時に止まるようにすることでした。また、WhozCraigのようにポインタを4回変更する必要があります。ここ はわずかに変更され、あなたのコードです：私のマシン上で働いていた

void swapElements1(struct node **head) //(not working)Function to swap first and last element of the list 
{ 
    struct node *current, *temp; 
    current = temp = *head; 

    while(current->next != NULL) 
    { 
     temp = current; 
     current = current -> next; 
    } 
    temp->next = *head; 
    current->next = (*head)->next; 
    (*head)->next = NULL; 
    *head = current; 
} 

。 whileループ状態をcurrentからcurrent-> nextに変更し、正しい "ポインタの変更"を行いました。これらのポインタの変更は説明が難しいので、通常は紙の上に作成してからコードに書きます。