Use Recursion is simpler and quicker


  • 8
    Y

    This problem could be solved by recursion, we first dig down to the middle node of the list, and recurse back from that point, the time complexity is O(N), and faster than existing algorithm.
    1 -> 2 ->3 ->4, first dig down to 3, then recurse back, concatenate 2->3 (which already together), then 1->4(we return next node of each node starting from middle one)

    public void reorderList(ListNode head){
    	      if(head == null || head.next == null) return;
    	      ListNode h = reorderList(head, head,head);
         }
    
    public ListNode reorderList(ListNode prev, ListNode slow, ListNode faster){
    	if(faster == null || faster.next == null) {
    		if(faster != null) {
                ListNode reverse = slow.next;
                slow.next = null;
    		    return reverse;
    		}
    		prev.next = null;
    		return slow;
    	}
    	ListNode retNode = reorderList(slow, slow.next, faster.next.next);
    	// concanate
    	ListNode temp = retNode.next;
    	retNode.next = slow.next;
    	slow.next = retNode;
    	return temp;
    }

  • 0
    H

    In the case of 1->2->3->4, the last node 3 will point to itself.


  • 0
    S

    Faster than which existing algorithm? I don't think it is any faster than reversing the second half and merging the two halves from both ends. By the way, your algorithm takes O(N) extra stack space, whereas the reversing-merging algorithm needs only O(1).


  • 0
    D

    A recursive c++ implementation.

    class Solution {
    public:
        bool reorderList(ListNode *&head, ListNode *tail)
        {
            if (!head) return false;
            
            if (!tail->next)
            {
                if (head==tail || head->next==tail) return false;
                ListNode *thead = head->next;
                head->next=tail;
                head=thead;
                return true;
            }
            
            if (!reorderList(head,tail->next)) return false;
            
            if (head==tail || head->next==tail) 
            {
                tail->next->next=head;
                tail->next=NULL;
                return false;
            }
            
            ListNode *thead = head->next;
            head->next=tail;
            tail->next->next=head;
            head=thead;
            return true;
        }
            
        void reorderList(ListNode *head) {
            reorderList(head,head);
        }
    };

  • 0
    J

    After viewing your code, I still prefer the iterative algorithm.


  • 0
    W

    recursion takes O(n) space


  • 0

    Your code failed the last test


Log in to reply
 

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