带哨兵的链表

Question

有一个链表，链表的每一端都有sentinel S(sentinel)->1->2->3->4->5->6->S（类似这样的东西）。我必须交换邻居元素：S->1->2->3->4->5->S 到 S->2->1->4->3->5->S 但代码这样做 instead:2->1->4->3->-842150451。此代码适用于每种输入：S->1->2->S、S->1->S 等。我必须在原始代码中建立新的列表连接。禁止更改节点中整数的值。我相信我的 void reverse_pairs(list* head) 功能不好，但我现在不知道如何让它工作。

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

typedef struct _list {
    int a;
    struct _list* next;
}list;
    

void reverse_pairs(list* head)
{
    if (head)
    {
        for (; head->next && head->next->next; head = head->next->next)
        {
            list* tmp = head->next;
            head->next = head->next->next;

            tmp->next = head->next->next;
            head->next->next = tmp;
        }
    }
}


list* makesentinel() 
{
    list* stra1 = (list *)malloc(1 * sizeof(list));
    list* stra2 = (list*)malloc(1 * sizeof(list));
    stra1->next = stra2;
    stra2->next = NULL;
    return stra1;
}
void push(list* head_ref, int new_data)
{
    list* new_list = (list*)malloc(sizeof(list));
    new_list->a = new_data;
    new_list->next = head_ref->next;
    head_ref->next = new_list;
}
void print(struct _list* node)
{
    list* temp = NULL;
    temp = node->next;
    while (temp->next != NULL) {
        printf("%d ", temp->a);
        temp = temp->next;
    }
}

int main()
{
    list* start = NULL;
    start = makesentinel();
    push(start, 5);
    push(start, 4);
    push(start, 3);
     push(start, 2);
     push(start, 1);

    printf("before\n");
    print(start);

    reverse_pairs(start);

    printf("\nafter\n");
    print(start);

    return 0;
}

Answer 1

你的问题是你从不测试最后一对是否完整。如果您的链接列表包含偶数个元素，则您的代码可以正常工作（只需尝试添加 push(start, 6);）。

所以你必须进一步测试 reverse_pairs:

void reverse_pairs(list* head)
{
    if (head)
    {
        for (; head->next && head->next->next && head->next->next->next; head = head->next->next)
        {
            ...

带哨兵的链表

Linked list with sentinel

c

pointers

linked-list

sentinel