修复反转 link

Question

嘿，出于某种原因，我的链表以相反的顺序打印，例如，如果我的输入是 2->4->6 我的输出是 6->4->2

list* add_int_list(list* a,int b)
{
    list *temp;
    temp = (list*)malloc(sizeof(list*));
    temp->next = NULL;
    if (a->next == NULL)//insert to the first node
    {
        temp->data = b;
        temp->next = a;
        a = temp;

    }
    else 
    {
        temp->data = b;
        temp->next = a;
        a = temp;//I think the problem is here, couldnt find how to fix 
}

Answer 1

问题是您的代码在这两种情况下都将节点附加到列表的前面。如果你想总是追加到列表的末尾，你需要遍历列表直到最后，然后在那里添加 temp。

这段代码是我即兴写的，所以当成伪代码吧：

// Assuming this function returns the front (head) of the list.
list* append_element_to_list(list* a, int b)
{
    list *newNode;
    newNode = (list*)malloc(sizeof(list*));
    newNode->data = b;

    // Handle the case where `a` is NULL. This means
    // no list was passed in, so the newly created node
    // will be returned to start the list.
    if (a == NULL)
    {
      return newNode;
    }

    // If we get this far, it means `a` contains at least
    // one node. So walk the list until the end.
    list *currentNode = a;
    while (currentNode->next != NULL)
    {
      currentNode = currentNode->next;
    }

    // Once you reach the end of the list, set
    // `newNode` as the last node.
    currentNode->next = newNode;

    // The front of the list hasn't changed, so return that.
    return a;
}

Answer 2

您的代码有一些错误，我正在对您的代码进行更正，只是更改需要的部分。首先我想关注主要问题，在插入任何列表的最后之前，您应该迭代完整列表。

  i = a; // to iterate
  while(i->next != NULL)
  {
   i = i->next;
  }
  // Now i is last node of list a
  i->next = temp;

下面的代码，我只是在 TurboC 上检查过，我正在使用你的函数并插入三个值，然后打印列表。请查看所有行注释：

#include <stdio.h>
#include <malloc.h>
typedef struct node{
 int data;
 struct node *next;

}list;

list* add_int_list(list* a,int b)
{
    list *temp;
    list *i;

    temp = (list*)malloc(sizeof(list*));
    temp->next = NULL;
    temp->data = b;

    if (a == NULL)//insert to the first node
    {
       //temp->data = b; -  done above
    //temp->next = a; no reason for this line
        a = temp;
    }
    else
    {
       // temp->data = b; - done above
       //temp->next = a; wrong logic
       // a = temp;//I think the problem is here, couldnt find how to fix : Yes it is also wrong

      //Here it required to iterate complete list and go to end

      i = a; // to iterate
      while(i->next != NULL)
      {
       i = i->next;
      }
      // Now i is last node of list a
      i->next = temp;
    }

    return a;
}
void printList(list *root)
{
   list *i;

   if(root == NULL)
   {
    printf("List is empty");
   }
   else
   {
    i = root;
    while(i != NULL){
      printf("%d,",i->data);
      i = i->next;
    }
   }
}
int main()
{
  list *root = NULL;
  clrscr();
  root =  add_int_list(root, 3);
  root =  add_int_list(root, 4);
  root =  add_int_list(root, 5);
  printList(root);
    return 0;
}

Answer 3

对于本声明中的初学者

temp = (list*)malloc(sizeof(list*));
                            ^^^^^

分配了大小等于指针大小而不是节点大小的内存。你必须写

temp = (list*)malloc(sizeof(list));

或

temp = (list*)malloc(sizeof( *temp));

这个if语句

if (a->next == NULL)

可以调用未定义的行为，因为最初列表可以是空的。所以指针a可以等于NULL。那就是使用了一个空指针来访问内存。

if-else 语句的 if 和 else 部分之后的这两个代码块没有区别

if (a->next == NULL)//insert to the first node
{
    temp->data = b;
    temp->next = a;
    a = temp;
}
else 
{
    temp->data = b;
    temp->next = a;
    a = temp;//
}

这两个代码片段都尝试在列表的开头插入一个新节点。

在单链表的开头插入一个新节点是一种通用的做法。将节点附加到这样的列表的末尾是低效的，因为必须遍历整个列表。

如果要将节点附加到单向链表的末尾，则将其设为双向。

这是一个演示程序。

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

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct List
{
    Node *head;
    Node *tail;
} List;

int push_front( List *list, int data )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = list->head;

        list->head = new_node;

        if ( list->tail == NULL ) list->tail = list->head;
    }

    return success;
}

int push_back( List *list, int data )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = NULL;

        if ( list->tail == NULL )
        {
            list->head = list->tail = new_node;
        }
        else
        {
            list->tail = list->tail->next = new_node;
        }
    }   

    return success;
}

void output( const List *list )
{
    for ( const Node *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

int main(void) 
{
    List list = { .head = NULL, .tail = NULL };

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        if ( i % 2 != 0 )
        {
            push_front( &list, i );
        }
        else
        {
            push_back( &list, i );
        }

        output( &list );
    }

    return 0;
}

它的输出是

0 -> null
1 -> 0 -> null
1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null
9 -> 7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null

在此演示程序中，使用函数 push_back 将偶数插入列表的末尾，使用函数 push_front.[=22 将奇数插入列表的开头=]

如果您的 C 编译器不支持指定的初始值设定项，则此声明

List list = { .head = NULL, .tail = NULL };

可以通过以下方式更改

List list = { NULL, NULL };

修复反转 link

fix for a reversed link

c

linked-list

insert

singly-linked-list