Объединить отсортированные связанные списки с головным узлом и без новых узлов (функция void)

Question

Я пишу пустую функцию void merged_lists (cell * l1, cell * l2, cell * l3);, которая получает два связанных списка во главе с l1 и l2 , содержимое которых упорядочено в неубывающем порядке, и генерирует новый список, возглавляемый l3 , который содержит элементы l1 и упорядоченного l2.

Если список, возглавляемый l1 , равен l1 -> 1 -> 7 -> 9 -> 10 -> NULL и возглавляется 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

Это объявление функции

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;
}

Answer 2

Не думаю, что вы можете решить эту проблему без переменной tmp. Переопределив указатель на следующий элемент в списке 1, вы в основном потеряете доступ ко всем элементам в списке 1 после текущего. Поэтому, если вы не сохраните последний фрагмент списка во временной переменной, это невозможно.