反转c中的单向链表并返回head

问题描述 投票:0回答:1

请问我缺少什么,我正在尝试反转单链表(就地),但我返回的只是一个节点(指向列表头的指针)。我尝试使用 void 函数(作为副作用)在 while 循环中使用相同的逻辑,但都给出相同的结果。 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;
}
c linked-list reverse
1个回答
0
投票

你只需要三个指针,

prev
curr
next
以及这四个语句,while
curr != NULL
,最后返回
prev

node *next = curr->next;
curr->next = prev;
prev = curr;
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
© www.soinside.com 2019 - 2024. All rights reserved.