Это вопрос объединения двух отсортированных списков. Я мог понять, в чем проблема?

Question

Программа принимает два отсортированных связанных списка и возвращает один связанный список путем объединения этих связанных списков. Я написал logi c с учетом крайних случаев, но вывода не ожидается. Думаю, проблема в формировании третьего связного списка. Я не могу сформировать третий связанный список.

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *l3 = new ListNode(0);
        ListNode *head = l3;
        ListNode *temp = new ListNode();
        if (!l1 && !l2) {
            return l1;
        } else if (!l1) {
            return l2;
        } else if (!l2) {
            return l1;
        } else if (l1->val <= l2->val) {
            l3->val = l1->val;
            l1 = l1->next;
        } else {
            l3->val = l2->val;
            l2 = l2->next;
        }
        while (l1->next || l2->next) {
            print(head);
            print(l1);
            print(l2);
            if (l1->val <= l2->val) {
                temp->val = l1->val;
                l1 = l1->next;
            } else {
                temp->val = l2->val;
                l2 = l2->next;
           }
            print(temp);
            //l3 = l3->next;
            l3->next = temp;
            l3 = l3->next;
        }
        return head;
    }
};

Answer 1

Ваша основная проблема заключается в том, что вы не выделяете новые узлы для каждого элемента в новом списке:

Вы начинаете с l3, который является новым ListNode, представляющим начало объединенного списка, и устанавливаете l3->val до правильного начального значения (минимум l1->val и l2->val). Позже вы делаете что-то подобное с temp, оценивая «текущие» узлы списков, на которые теперь указывают l1 и l2, и устанавливаете temp->val как минимум из двух. Проблема заключается в том, что l1, l2, l3 и temp - все указатели на ListNodes. Вы неоднократно устанавливаете l3-> next, чтобы указывать на один и тот же фрагмент памяти (на который указывает temp), причем базовый член значения перезаписывается на каждой итерации l oop. Я бы посоветовал думать о работе temp как о «передаче» ListNode, на который он указывает (становится l3->next), и изменении для указания на новый фрагмент памяти для хранения нового ListNode (для следующей итерации) или еще лучше полностью избавьтесь от температуры, извлекая min value из l1 или l2 и выполнив простой l3->next = new ListNode(min_val). Было бы полезно нарисовать диаграмму памяти с l1, l2 и l3, буквально указывающими на отдельные части памяти, таким образом вы можете перемещать стрелки и улавливать еще несколько крайних случаев.

Несколько других вещей, которые может сбить вас с толку:

1) Подумайте о своем состоянии l oop - вы установили (как до, так и в l oop) l1 = l1->next или l2 = l2->next и перешли к это новое значение next член в условии l oop без проверки того, было ли само это новое значение нулевым. Эта ловушка (нулевое разыменование) также может повлиять на проверку члена val, когда вы дошли до конца одного списка, но не дошли до конца другого.

2) Ваше начальное l3->val равно 0, и при использовании произвольного числа - не самая лучшая практика. Это было бы отличным временем для консолидации, что-то вроде ListNode* l3 = new ListNode(min(l1->val, l2->val)) после проверки того, что l1 и l2 не равны нулю.

3) Ваше самое первое условие бесполезно, потому что (если я предполагаю правильно возвращать null, если оба списка пусты) один список является пустым, просто означает, что возврат другого списка верен, что в любом случае происходит с помощью следующих двух условий.

Надеюсь, это поможет!

Answer 2

Если целью является объединение списков, вы не должны выделять новые узлы, а просто измените элементы next, чтобы сформировать единый упорядоченный список. Есть 2 фазы:

• , пока у вас есть узлы в обоих списках, сравните головной узел, чтобы определить, из какого списка взять первый элемент, и свяжите его с объединенным списком.
• когда один из списков исчерпан, свяжите другой список в конце объединенного списка.

Чтобы связать элемент в конце объединенного списка, вы держите указатель на последний node.

Вот измененная версия:

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = NULL;
        ListNode *tail = NULL;
        ListNode *n;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                n = l1;
                l1 = l1->next;
            } else {
                n = l2;
                l2 = l2->next;
            }
            if (tail) {
                tail = tail->next = n;
            } else {
                tail = head = n;
            }
        }
        if (l1) {
            n = l1;
        } else {
            n = l2;
        }
        if (tail) {
            tail->next = n;
        } else {
            head = n;
        }
        return head;
    }
};

Освоив двойные указатели, вы можете улучшить этот код и удалить тесты для головного узла:

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = NULL;
        ListNode **nextp = &head;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                *nextp = l1;
                nextp = &l1->next;
                l1 = l1->next;
            } else {
                *nextp = l2;
                nextp = &l2->next;
                l2 = l2->next;
            }
        }
        *nextp = l1 ? l1 : l2;
        return head;
    }
};