Sharing my 16 ms Cpp solution ; beats 99.54%


  • 1
    G

    class Solution {
    public:
    ListNode* oddEvenList(ListNode* head) {

        if(!head || !head->next)
            return head;
        
        int count = 1;
        ListNode *oddHead = head,*oddTail = head; 
        ListNode *evenHead = head->next,*evenTail = head->next;
        ListNode *temp = evenHead->next;
        oddHead->next = NULL;
        evenHead->next = NULL;
        
        while(temp != NULL)
        {
            if(count%2 == 1)
            {
                oddTail->next = temp;
                oddTail = temp;
                temp = temp->next;
                oddTail->next = NULL;
            }
            else
            {
                evenTail->next = temp;
                evenTail = temp;
                temp = temp->next;
                evenTail->next = NULL;   
            }
            count++;
        }
        
        oddTail->next = evenHead;
        return oddHead;
    }
    

    };


  • 0

    @gaurav.nijhara Hi, I wrote the same code with yours except this part:

    oddHead->next = NULL;
    evenHead->next = NULL;
    

    So I got an error. Why we need to set oddHead->next and evenHead->next to be NULL? At the end, return oddHead, but we set the oddHead->next = NULL, how to expect to return a valid oddHead?

    I haven't used Linked List for a long time. My question may be a little stupid.

    And I use Swift language to solve this question using the same solution. My run time is 236 ms, why is it so different with yours?


  • 1
    G

    @zhugejunwei : the goal is to try to keep two separate linked lists and merge them in the end . I wrote the following statements

    ListNode *oddHead = head,*oddTail = head; 
    ListNode *evenHead = head->next,*evenTail = head->next;
    

    before -:

    oddHead->next = NULL;
    evenHead->next = NULL;
    

    The above statements mean that I have my odd linked list's head pointing to the input linked list's head and even linked list's head pointing to input linked list's head->next . Setting oddHead and evenHead to NULL breaks the first two elements into heads to two different linked lists . The rest of the logic carries from just adding alternate nodes to each linked list .

    I can't say why it takes more time in swift , maybe swift's compiler is slower that cpp for the above operations .


  • 0

    @gaurav.nijhara At the beginning, I didn't quite understand what you mean about "Setting oddHead and evenHead to NULL breaks the first two elements into heads to two different linked lists".

    So I searched a lot about the head node of a linked list. I still have a question. Why don't you need to set oddHead->next = oddTail, and so does evenHead. Because oddHead links with oddTail, and then we can do the following operation on oddTail to add nodes.

    Many people said head node is a reference of the first node of a linked list, but in C++, it's declared by *, which is known as a pointer. Well, in this question, are the oddHead and evenHead two absolute nodes or references (pointers) to the first node?

    Thank you very much!


  • 1
    G

    @zhugejunwei : oddHead, evenHead, oddTail and evenTail are all pointers . Yes you read correct , a conventional linked list only has head pointer . I maintain a tail pointer which points to the last element of the lists respectively because it saves us the overhead of traversing the list every time to the end to insert a new node . Nodes need to be inserted at the end of respective lists to preserve the order of the input .


  • 0
    J
    class Solution {
    public:
        ListNode* oddEvenList(ListNode* head) {
            if(!head || !head->next)
    			return head;
    		ListNode* Oddhead=head;
    		ListNode* Evenhead=head->next;
    		ListNode* Odd=Oddhead;
    		ListNode* Even=Evenhead;
    		int index=1;
    		head=head->next->next;
    		while(head!=NULL)
    		{
    			if(index%2==0)
    			{
    				Even->next=head;				
    				Even=Even->next;
    			}
    			else if(index%2==1)
    			{		
    				Odd->next=head;
    				Odd=Odd->next;
    			}
    			head=head->next;
    			index++;
    		}
    		Odd->next=Evenhead;
    		return Oddhead;
        }
    };
    

    Hi, this is my solution ,and my thoughts are the same with you.But I can't figure out why my CPP cannot pass the case [1,2,3],can you help me? Thanks a lot


  • 0

    @gaurav.nijhara It's been a long time, I can't stop thinking about the oddHead and evenHead everyday. Finally I understand what oddHead->next = NULL; means. Thank you very much!


Log in to reply
 

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