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

Это явно не так:

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

Это просто перезаписывает предыдущее значение со значением temp. Первое утверждение также не может быть даже там.

Вам принципиально нужно два свопы (технически один плюс уступки и терминации)

• указатели, указывающие на двух узлов
• два узла next указатели

Последний из этих ISN Технически необходимо, но прямое назначение -, а новый хвост должен иметь next, установленный в null, чтобы прервать новый список.

Полный пример показан ниже, либерально прокомментированный, мы надеемся, предоставим алгоритм происходящего.

#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 уже совершенен, но, возможно, вам захочется увидеть свой собственный код с некоторыми настройками. В основном, я сделал это, чтобы остановить поиск последнего элемента одной итерации раньше, чтобы temp остановился на 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 while от current to current-> next и сделал правильные «изменения указателя». Эти изменения указателя трудно объяснить, обычно я делаю их на бумаге сначала, а затем записываю их в код.