合并带有头节点但没有新节点的排序链表（void 函数）

Question

我正在编写一个 void 函数 void merged_lists (cell * l1, cell * l2, cell * l3);，它接收两个链表，以 l1 和 l2 为首，其内容以非递减顺序排列，并且生成一个以 l3 为首的新列表，其中包含有序的 l1 和 l2 的元素。

如果以l1为首的列表是l1 -> 1 -> 7 -> 9 -> 10 -> NULL 并且为首by l2是l2 -> 2 -> 3 -> 8 -> NULL，比如输出一定是l3 -> 1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> NULL

这是一个已知解决方案的问题，但我正在尝试解决它 而不在函数中分配任何新单元格，只是操纵来自 l 节点的指针位于 l1 和 l2.

我的做法：

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

void merged_lists (cell * l1, cell * l2, cell * l3){

    if(l1->next == NULL)
        l3 = l2->next;
    if(l2->next == NULL)
        l3 = l1->next;
    if(l1->next->data <= l2->next->data)
        l3 = l1->next;
    else
    {
        l3 = l2->next;
        l2->next->next = l1->next;

    }

while(l1->next && list2->next) {
    if (l1>next->data > l2->data) {
    //Step 1. Save the next pointer
      Node *tmp = l1->next; 
    //Step 2. Change next pointer to point L2
      l1->next = l2;
    //Step 3. Move L2 to temp
      l2= tmp;
    }
    //Step 4. Move L1 ahead
    l1 = l1->next;
  } 
  if (!l1->next)
 l1->next = l2;





}

在主函数中我将l3作为参数传递给print(cell * head)

关于如何修复该解决方案的一些提示？

Answer 1

如果没有 tmp 变量，我认为您无法解决此问题。一旦覆盖了列表 1 中下一项的指针，您基本上就无法访问列表 1 中当前项目之后的所有项目。因此，除非您将列表的最后一部分存储在临时变量中，否则这是不可能的。

Answer 2

这个函数声明

void merged_lists (cell * l1, cell * l2, cell * l3);

无效，因为指针是按值传递的。那就是该函数处理指向列表头节点的原始指针的副本。因此，原始指针将不会更改。

这是一个演示程序，展示了如何声明和定义函数。

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

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

size_t append( cell **head, const int a[], size_t n )
{
    size_t i = 0;

    if ( n )
    {
        while ( *head != NULL ) head = &( *head )->next;

        for ( ; ( i < n ) && ( ( *head = malloc( sizeof( cell ) ) ) != NULL ); i++ )
        {
            ( *head )->data = a[i];
            ( *head )->next = NULL;
            head = &( *head )->next;
        }
    }

    return i;
}

void display( const cell *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }

    puts( "NULL" );
}

cell * merged_list( cell **list1, cell **list2 )
{
    cell *list3 = NULL;

    cell **current = &list3;

    while ( *list1 != NULL && *list2 != NULL )
    {
        if ( ( *list2 )->data < ( *list1 )->data )
        {
            *current = *list2;
            *list2 = ( *list2 )->next;
        }
        else
        {
            *current = *list1;
            *list1 = ( *list1 )->next;
        }

        current = &( *current )->next;
    }

    for ( ; *list1 != NULL; current = &( *current )->next )
    {
        *current = *list1;
        *list1 = ( *list1 )->next;
    }

    for ( ; *list2 != NULL; current = &( *current )->next )
    {
        *current = *list2;
        *list2 = ( *list2 )->next;
    }

    return list3;
}

int main(void) 
{
    cell *list1 = NULL;
    cell *list2 = NULL;

    int a1[] = { 1, 7, 9, 10 };
    int a2[] = { 2, 3, 8 };

    append( &list1, a1, sizeof( a1 ) / sizeof( *a1 ) );
    append( &list2, a2, sizeof( a2 ) / sizeof( *a2 ) );

    display( list1 );
    display( list2 );

    putchar( '\n' );

    cell *list3 = merged_list( &list1, &list2 );

    display( list1 );
    display( list2 );
    display( list3 );

    return 0;
}

程序输出为

1 -> 7 -> 9 -> 10 -> NULL
2 -> 3 -> 8 -> NULL

NULL
NULL
1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> NULL

函数merged_list可以写得更短

cell * merged_list( cell **list1, cell **list2 )
{
    cell *list3 = NULL;

    cell **current = &list3;

    while ( *list1 != NULL || *list2 != NULL )
    {
        if ( *list1 == NULL || ( *list2 != NULL && ( *list2 )->data < ( *list1 )->data ) )
        {
            *current = *list2;
            *list2 = ( *list2 )->next;
        }
        else
        {
            *current = *list1;
            *list1 = ( *list1 )->next;
        }

        current = &( *current )->next;
    }

    return list3;
}

合并带有头节点但没有新节点的排序链表（void 函数）

Merge Sorted Linked Lists with head node and without new nodes (void function)

c

merge

mergesort

linked-list

singly-linked-list