Reorder list, time limit exceeded


  • 0
    Q

    My solution is:

    public class Solution {

    public void reorderList(ListNode head) {
    
        if (head == null || head.next == null || head.next.next ==null) return;
        
        ListNode h1 = head;
        ListNode h2 = head;
        ListNode h3 = head.next;
        
        while (h3.next != null) {
            h2 = h2.next;
            h3 = h3.next;
        }
        h2.next = null;
        h3.next = h1.next;
        h1.next = h3;
        reorderList(h3.next);
    }
    

    }

    I think my code is very concise. And I tested on small cases , such as 12345,123456, I got right answer. But since it must be in place. I do not know how to improve that. Thanks for any replies.


  • 2
    W

    Think about the time complexity. The time complexity of your algorithm is O(N^2), this is inefficient.

    You can try to use a stack to solve this problem in O(N).


  • 0
    Q

    Thanks. It passed.

    public class Solution {
    public void reorderList(ListNode head) {

        Stack<ListNode> s = new Stack<ListNode>();
        if (head == null || head.next == null || head.next.next ==null) return;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        while (slow.next != null) {
            s.push(slow.next);
            slow = slow.next;
        }
        
        ListNode h1 = head;
        if (fast.next == null) {
            while (!s.empty()) {
                ListNode cur = s.pop();
                cur.next = h1.next;
                h1.next = cur;
                h1 = cur.next;
            } 
            h1.next = null;
            return;
        } else {
            while (!s.empty()) {
                ListNode cur = s.pop();
                if (s.empty()) {
                    cur.next = null;
                    h1.next = cur;
                    return;
                } else {
                    cur.next = h1.next;
                    h1.next = cur;
                    h1 = cur.next;
                }
            }
        }
    }
    

    }


  • 0
    Q

    let me know how to make it more concise. I judge the two scenario , node # is even or odd when I have to pop up the node from the stack. Any other ways?


  • 0
    S

    @queenleet, could you please ask another question, or related question about your new solution how to be concise? When you do it, remember to add some words about algorithm and comment in code, then hide these comments. Thanks.


  • 0
    S

    Could you please correct the code format? Did you update the question? Could you organize your comments in answer into question post, then hide the comments? Thanks.


  • 0
    Q

    I do not know how to do it.How and what is to organize my comments in answer into question post?


  • 0
    S

    @queeleet, I thought you have a tle question before, then you solved it, later you want to make your solution more concise, which you mentioned in the comments below in walkerix's answer. And now, you ask the 3rd question something about 'in place'. Am I right? Next time you do it, you can ask a related question of an answer, or just a new question of a totally different purpose.


Log in to reply
 

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