Reorder in O(n), but code seems a little redundancy


  • 1
    S
    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(head){
                int len = 0;
                ListNode* tmp = head;
                while(tmp){
                    len++;
                    tmp = tmp->next;
                }
                len = len/2;
                tmp = head;
                while(len--) tmp = tmp->next; //tmp point to the mid node;
                ListNode* head2 = tmp->next;
                tmp->next = NULL;
                head2 = reverseList(head2);
                head = mergeLinkedList(head, head2);
            }
        }
        
        //reverse a linked list.
        ListNode* reverseList(ListNode* head) {
            if(head == NULL || head->next == NULL) return head;
            ListNode *pre = head, *cur = head->next, *next;
            pre->next = NULL;
            while(cur){
                next = cur->next; //save the next node;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
            
        }
        //merge link list h1 and h2;
        ListNode* mergeLinkedList(ListNode* h1, ListNode* h2)
        {
            if(!h1) return h2;
            if(!h2) return h1;
            ListNode* tmp1 = h1->next, *tmp2 = h2, *h = h1, *tmp = h;
            int i = 1;
            while(tmp1 && tmp2){
                if(i%2 == 0){
                    tmp->next = tmp1;
                    tmp1 = tmp1->next;
                }
                else{
                    tmp->next = tmp2;
                    tmp2 = tmp2->next;
                }
                tmp = tmp->next;
                i = (i+1) % 2;
            }
            if(tmp1) tmp->next = tmp1;
            else if(tmp2) tmp->next = tmp2;
            else tmp->next = NULL;
            return h;
        }
    };

  • 1
    B

    One redundancy I see is in the way to get the middle node.
    For finding the mid node, you can reduce on extra pass by taking two pointers, and incrementing one pointer at the speed of one node at a time, and the other one at double the speed. When the latter reaches null, guess where the first pointer would be?


  • 0
    N

    I am using the similar idea. For the method mergeLinkedList, it can be cleaner, like this:

        ListNode *appendNode(ListNode* tail, ListNode *node)
    {
    	tail->next = node;
    	return tail->next;
    }
    
    ListNode *merge(ListNode *head1, ListNode *head2)
    {
    	ListNode *head = head1;
    	head1 = head1->next;
    	ListNode * tail = head;
    	while (head1 != nullptr)
    	{
    		tail = appendNode(tail, head2);
    		head2 = head2->next;
    		tail = appendNode(tail, head1);
    		head1 = head1->next;		
    	}
    	appendNode(tail, head2);
    	return head;
    }
    

    Is it better?


Log in to reply
 

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