Is the sorted list descendant or ascendant?


  • 0
    C

    ...or should I find out through the input? If I should determine the order, then what should it be when the inputs are two single-element lists? Thanks!


  • 10
    P

    You can safely assume that they are both ascendant.


  • 1
    H

    Generally, without explicit declaration, sorted lists or sorted array means ascendant.

    and you can just do it as ascendant, if it's descendant, your code cannot get accepted and the wrong info will tell you that it is descendant. In this situation, I believe you can revise your code simply, just turn '>' to '<' or turn ‘<’ to '>'

    ..


  • 0
    S

    My code simply try to fit in two case.
    note: for {2} {1} , it outputs {1 2} by default ascendant

    class Solution {
    public:
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            if( l1==NULL)
                return l2;
            if( l2==NULL)
                return l1;
         
            bool isDecreasing = true;
            ListNode *temp = l1;
            while(temp->next != NULL)
            {
                if(temp->val != temp->next->val)
                {
                    isDecreasing = temp->next->val > temp->val;
                    break;
                }
                temp = temp->next;
            }
            temp = l2;
            while(temp->next != NULL)
            {
                if(temp->val != temp->next->val)
                {
                    isDecreasing = temp->next->val > temp->val;
                    break;
                }
                temp = temp->next;
            }
            ListNode *newList = NULL;
            ListNode *secondList = NULL;
            if(isDecreasing)
            {
                if(l1->val <= l2->val)
                {
                    newList = l1;
                    secondList = l2;
                }
                else
                {
                    newList = l2;
                    secondList = l1;
                }
                
                ListNode *p = newList;
                ListNode *p2 = secondList;
                do
                {
                    if(p->next == NULL)
                    {
                        p->next = p2;
                        return newList;
                    }
                    if(p2->val < p->next->val)
                    {
                        ListNode *t = p2->next;
                        
                        p2->next = p->next;
                        p->next = p2;
                        
                        p = p2;
                        p2 = t;
                    }
                    else if(p2->val >= p->next->val)
                    {
                        p = p->next;
                    }
                }while(p2 != NULL); 
                
            }
            else
            {
                if(l1->val >= l2->val)
                {
                    newList = l1;
                    secondList = l2;
                }
                else
                {
                    newList = l2;
                    secondList = l1;
                }
                
                ListNode *p = newList;
                ListNode *p2 = secondList;
                do
                {
                    if(p->next == NULL)
                    {
                        p->next = p2;
                        return newList;
                    }
                    if( p2->val > p->next->val)
                    {
                        ListNode *t = p2->next;
                        
                        p2->next = p->next;
                        p->next = p2;
                        
                        p = p2;
                        p2 = t;
                    }
                    else if(p2->val <= p->next->val)
                    {
                        p = p->next;
                    }
                }while(p2 != NULL); 
            }
            
            return newList;
          
            
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.