C：合并排序的链接列表-仅移动指针

von4xj4u 于 2022-12-02 发布在其他

关注(0)|答案(1)|浏览(119)

我有两个已排序的链表，list 1和list 2。我的目标是将list 2合并到list 1中。
所需经费如下：
1.结果列表应该是list 1（不创建新的链接列表，也不使合并列表位于新的链接列表中）
1.返回类型必须为void
1.合并后list 2必须为空
1.合并列表必须排序
1.无法删除或移除任何节点。仅移动指针
1.无递归
1.算法中不允许排序
1.无其他帮助函数
示例输出：

列表1：d -〉e -〉f -〉t -〉w -〉x -〉y -〉空
列表2：a -〉B -〉e -〉j -〉l -〉z -〉空

结果：

列表1：a -〉B -〉d -〉e-〉e -〉f -〉j -〉l -〉t -〉w -〉x -〉y -〉z -〉空
列表2：空

我的程式码结果目前是

列表1：d -〉e -〉f -〉j -〉l -〉t -〉w -〉x -〉y -〉z -〉空
列表2：a -〉B -〉d -〉e-〉e -〉f -〉j -〉l -〉t -〉w -〉x -〉y -〉z -〉空

typedef struct listNode {
        char data;
        struct listNode* nextPtr;
} ListNode;
        
typedef ListNode* ListNodePtr;

void mergeSortedList(ListNodePtr list1, ListNodePtr list2) {

    ListNodePtr curr = NULL;
    ListNodePtr last = NULL;

    if (list1->data < list2->data)
    {
        curr = list1;
        last = list1;
        list1 = list1->nextPtr;
    }
    else {
        curr = list2;
        last = list2;
        list2 = list2->nextPtr;
    }
    last->nextPtr = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data < list2->data) {
            last->nextPtr = list1;
            last = list1;
            list1 = list1->nextPtr;
        }
        else {
            last->nextPtr = list2;
            last = list2;
            list2 = list2->nextPtr;
        }
        last->nextPtr = NULL;
    }

    if (list1 != NULL) {
        last->nextPtr = list1;
    }
    else {
        last->nextPtr = list2;
    }
}

c

来源：https://stackoverflow.com/questions/74588586/c-merging-sorted-linked-list-move-pointers-only

1条答案

按热度按时间

ryevplcw1#

1.删除ListNodePtr，以支持ListNode *（请参阅Is it a good idea to typedef pointers?）。
1.正如@n.m.所暗示的，您需要传入ListNode **，以便对调用者产生影响。
1.如果list1或list2为NULL，则原始代码为segfaults。
1.如果*list1没有指向最小的第一个节点，则交换这两个列表，然后使用指针l1和l2遍历这两个列表。有趣的例子是将节点从l2移动到l1。这需要您提前查看l1 m上的节点，以便将入站指针设置为要移动的节点。或者，在l1上保留一个指针，指向当前节点的前一个节点。最后，处理l2上剩余的节点。

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

typedef struct listNode {
    char data;
    struct listNode* nextPtr;
} ListNode;

ListNode *createList(const char *data) {
    if(!data || !*data) return NULL;
    size_t n = strlen(data);
    ListNode *head = malloc(n * sizeof(*head));
    if(!head) return NULL;
    ListNode *p = head;
    for(size_t i = 0; i < n; i++, p = p->nextPtr) {
        p->data = data[i];
        p->nextPtr = p + 1;
    }
    (p-1)->nextPtr = NULL;
    return head;
}

void mergeSortedList(ListNode **list1, ListNode **list2) {
    if(!*list1 || (*list2 && (*list1)->data > (*list2)->data)) {
        ListNode *tmp = *list1;
        *list1 = *list2;
        *list2 = tmp;
    }
    if(!*list1) return;
    ListNode *l1 = *list1;
    ListNode *l2 = *list2;
    while(l1->nextPtr && l2) {
        if(l1->nextPtr->data <= l2->data)
            l1 = l1->nextPtr;
        else {
            ListNode *tmp = l2->nextPtr;
            l2->nextPtr = l1->nextPtr;
            l1->nextPtr = l2;
            l2 = tmp;
        }
    }
    if(l2) l1->nextPtr = l2;
    *list2 = NULL;
}

void printList(const char *name, ListNode *head) {
    printf("%s: ", name);
    for(; head; head = head->nextPtr) {
        printf("%c -> ", head->data);
    }
    printf("NULL\n");
}

int main(void) {
    ListNode *l1 = createList("deftwxy");   
    ListNode *l2 = createList("abejlz");
    mergeSortedList(&l1, &l2);
    printList("list1", l1);
    printList("list2", l2);
}

和结果输出：

list1: a -> b -> d -> e -> e -> f -> j -> l -> t -> w -> x -> y -> z -> NULL
list2: NULL

赞(0）回复(0）举报 2022-12-02

我来回答

C：合并排序的链接列表-仅移动指针

1条答案

相关问题

热门标签

最新问答