Warm tip: This article is reproduced from serverfault.com, please click

c-交换单向链表中的第一个和最后一个元素

(c - Swap first and last element in singly linked list)

发布于 2016-11-02 20:52:14

我想要做的是交换单向链表的第一个和最后一个元素。到目前为止,我有以下代码,我在其中创建了一个列表并向其中添加了一些数字。我的问题出在 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

这是一个演示

Questioner
user3120283
Viewed
0
WhozCraig 2016-11-03 05:26:30

这显然是错误的:

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

这只是用 的值覆盖了先前的值temp第一个陈述甚至可能不存在。

你从根本上需要两次交换(技术上一次加上一次分配和终止)

  • 指向两个节点的指针
  • 两个节点next指针

后者的这些在技术上并不需要,而是直接分配需要,新的尾部都需要有它的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 

我已经为你留下了清单清理工作(毫无疑问,你已经编写了这样的算法)。这其中的关键是如何使用指向指针的指针来操作链表的指针;不仅仅是一堆临时指针。我强烈建议你在调试器中单步执行交换功能,观察每一步发生的情况。