反转C中的单链表并返回新头

Question

请问我错过了什么？ 我试图反转单链表（就地），但我返回的只是一个节点（指向列表头部的指针）。我尝试在 while 循环中使用相同的逻辑使用 void 函数（作为副作用），但都给出相同的结果。

previus_node

为NULL，

current_node

指向head，而

next_node

指向head->next。 while循环运行到

current_node == NULL

，对于第一个节点，应该是最后一个，它通过说

current_node->next = previus_node

指向NULL（最初为NULL），然后将

previus_node

设置为

current_node

以开始下一次迭代，然后将

current_node

向前移动一个位置到

current_node->next

。

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

typedef struct node
{
    // holds number of type int
    int number;
    // holds pointer to node of the same type
    struct node *next;
} node;


// reverse link list
node *reverse(node *);

// create new node
node *create_node(int );

void print_list(node *head);

int main(void)
{
    // declare head node
    node *head = NULL;
    
    int numb2[] = {2,3,1,4,0,9,7};
    
    for (int i = 0; i < sizeof(numb2) / sizeof(int); i++)
    {
        head = insert_begining(head, create_node(numb2[i]));
    }        
    
    head = reverse(head);
    
    print_list(head);

    // free pointers
    destroy(head);
 }

// create linked list and return pointer to the list head
node *create_node(int n)
{
    // 1 dynamically allocate space for new node (linked list) of type node *
    node *new = (node*) malloc(sizeof(node));
    // 2 check to make sure we didin run out of memory
    if (new == NULL)
    {
        return NULL;
    }
    // 3 init nodes value field
    new->number = n;
    // 4 init nodes next field
    new->next = NULL;
    // 5 return pointer to a newly created node*
    return new;
}

// prints link list
void print_list(node *head)
{
    // TODO print in asc and desc
    // print elements of link list
    if (head == NULL)
    {
        printf("NULL");
    }
    // else not NULL
    while (head != NULL)
    {
        printf("%i, ", head->number);
        head = head->next;
    }
    printf("\n");



// reverse list
node *reverse(node *head)
{
    if (head == NULL)
    {
        return NULL;
    }
    
    node *previus_node = NULL;
    node *current_node = head;
    
    
    while (current_node != NULL)
    {
        current_node->next = previus_node;
        previus_node = current_node;
        
        // move current node forward by 1
        current_node = current_node->next;
    }
    
    return head;
}

Answer 1

你只需要三个指针，

prev

，

curr

和

next

以及这四个语句，while

curr != NULL

，最后返回

prev

：

node *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;

• node *next = curr->next;

  ：在更改

  curr->next

  指针之前，我们应该将下一个节点的地址保存在

  next

  变量中。

• curr->next = prev;

  ：这里我们反转

  curr

  节点指针的方向。

• prev = curr;

  ：我们将

  prev

  节点更新为

  curr

  节点。

• curr = next;

  ：我们将

  curr

  节点更新为

  next

  节点。

代码

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

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

node *reverse(node *head);
node *create_node(int n);
void display(node *head);
node *add_node(node *head, node *node);
void destroy(node *head);

node *create_node(int n) {
  node *new = (node *)malloc(sizeof(node));
  if (new == NULL) {
    return NULL;
  }
  new->number = n;
  new->next = NULL;
  return new;
}

void display(node *head) {
  while (head != NULL) {
    printf("%i\t", head->number);
    head = head->next;
  }
  printf("\n\n");
}

node *reverse(node *head) {
  node *prev = NULL;
  node *curr = head;
  while (curr != NULL) {
    node *next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

node *add_node(node *head, node *node) {
  node->next = head;
  return node;
}

void destroy(node *head) {
  while (head != NULL) {
    node *temp = head;
    head = head->next;
    free(temp);
  }
}

int main(void) {
  node *head = NULL;
  int nums[] = {2, 3, 1, 4, 0, 9, 7};

  for (int i = 0; i < sizeof(nums) / sizeof(int); i++) {
    head = add_node(head, create_node(nums[i]));
  }
  display(head);
  display(reverse(head));
  destroy(head);
}

打印

7   9   0   4   1   3   2   

2   3   1   4   0   9   7