降序链表合并

桃扇骨 2022-09-14 02:27 192阅读 0赞

题目：将两个降序链表合并为一个新的 降序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  
如：\{6,5,1\}\{8,5,2\} 合并后：\{8,6,5,5,2,1\}

ListNode* MergeTwoLists(ListNode* list1, ListNode* list2)
    {
        
        // write code here
        ListNode* node = new ListNode(-1);
        ListNode* node_0 = node;//备份头
    
        while (list1 ||  list2)
        {
        
    
            if (NULL == list1)
            {
        
                node->next = list2;
                return node_0->next;
            }
    
            if (NULL == list2)
            {
        
                node->next = list1;
                return  node_0->next;
            }
    
            if (list1->val >= list2->val)
            {
        
                node->next = list1;
                list1 = list1->next;
                node = node->next;
                node->next = NULL;//此处注意。先移List1后，再node->next = NULL；否则会把list1 设置NULL
    
            }
            else
            {
        
                node->next = list2;
                list2 = list2->next;
                node = node->next;
                node->next = NULL;
            }
        }
    /*  考虑内存泄漏
        node = node_0;
        node_0 = node_0->next;
        delete node;
        return node_0;
    */
        return node_0->next;
    }

此题考察的单链表操作。返回值还必须是链表头。验证下

int main()
    {
        
        ListNode* node_1 = new  ListNode(6);
        ListNode* node_2 = new  ListNode(5);
        ListNode* node_3 = new  ListNode(1);
        node_1->next = node_2;
        node_2->next = node_3;
        
        ListNode* node_4 = new  ListNode(8);
        ListNode* node_5 = new  ListNode(5);
        ListNode* node_6 = new  ListNode(2);
        node_4->next = node_5;
        node_5->next = node_6;
    
        ListNode* a_list =  MergeTwoLists(node_1,node_4);
        while (a_list)
        {
        
            cout << a_list->val<<" ";
            a_list = a_list->next;
        }
        cout << endl;
        return 0;
    }