Merge Two Sorted Lists

ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }

延伸:
在两个有序链表中查找第K大元素。 思路:和有序链表合并思路一样,不过在合并过程中需添加计数,同时需要注意相同大小元素只记1次。

Leave a Reply

Your email address will not be published. Required fields are marked *