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

내가이 필요한 것 :

목록은 다음과 같습니다 8 7 2 5 6

새 목록 : 6 7 2 5 8

,

여기이 분명히 잘못이다 demo

Answer 1

입니다 : 단지 temp의 값이 이전 값을 덮어 씁니다

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

합니다. 첫 번째 문장은 거기에있을 수도 있습니다.

당신은 근본적으로

두 개의 노드를 두 노드에 next 포인터

이 ISN의 후자를 가리키는 두 개의 스왑 (기술적 과제 더한 및 종료)

• 포인터가 필요합니다 기술적으로는 필요하지 않지만 직접 할당 은이고 새 꼬리에는 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와 같은 포인터를 사용하여 네 가지 변경 작업을 수행해야합니다. 여기에 약간 수정 된 코드입니다 :

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-> 다음으로 변경하고 올바른 "포인터 변경"을 수행했습니다. 이 포인터 변경은 설명하기 어렵습니다. 보통 종이로 작성한 다음 코드로 작성합니다.