时间戳

首页 > 解决方案 > 反转偶数的子列表

c - 反转偶数的子列表

问题描述

我正在尝试反转偶数的子列表。代码中似乎存在逻辑错误，但我找不到它。

    node *sublist_reverse(node *head)
    {
        node *temp=head,*wrking,*wrking_bfr,*node_tobe_ext;
        while(temp!=NULL)
        {
            if(temp->link->data%2==0)
            {
                while(temp->link->data%2==0)
                {
                    if(temp->data%2!=0)
                    {
                        wrking_bfr=temp;
                        wrking=wrking_bfr->link;
                    }
                    node_tobe_ext=wrking->link;
                    wrking->link=node_tobe_ext->link;
                    node_tobe_ext->link=wrking_bfr->link;
                    wrking_bfr->link=node_tobe_ext;
                    temp=wrking->link;
                }
            }
            else
            {
                temp=temp->link;
            }
        }
        return head;
    }

标签： calgorithmlinked-listreversesingly-linked-list

解决方案

我正在尝试反转偶数的子列表。

从提供的代码看来，您要做的是反转连续偶数的每个最大子列表，而不仅仅是一个。此外，这显然是在单链表的上下文中，与数组或双向链表相反。此外，我从定义为结构类型的代码中推断出node，至少包含成员dataand link，所以也许

struct node {
    int data;
    struct node *link;
};

typedef struct node node;

有了这些理解，您的想法似乎是扫描列表以找到偶数子列表的开头，反转该子列表，然后重复。这会产生代码中呈现的嵌套循环结构，这是解决问题的可行方法。

请有人告诉我我的逻辑错误是什么。

目前尚不清楚您在实现中发现了哪些具体问题或不当行为，但从代码中可以明显看出以下一些问题：

  • 当外部循环到达列表末尾时，当函数计算时，会发生不好的事情

        if(temp->link->data%2==0)

    这是因为当temp指向最后一个节点时，temp->link不是一个有效的节点指针。

  • 当内部循环到达列表的末尾时也会发生坏事，当最后一个元素是偶数时会发生这种情况。这些是有问题的行：

               node_tobe_ext=wrking->link;
           wrking->link=node_tobe_ext->link;

    当wrking指向最后一个节点时，node_tobe_ext不是一个有效的节点指针。

  • 当列表包含两个或更多偶数的初始子列表时，则不能正确反转。可以看出肯定是这样的，因为第一个列表元素的奇偶校验甚至从未被检查过，而且函数总是返回原始head指针。（如果有两个或更多偶数的初始子列表，则原始头节点将不是最终列表的头。）

推荐阅读