Error in my implementation.


  • -1
    P

    Hi. I want to solve this problem using a Stack and a LinkedList (I know it can be solved with a different approach) and I've debugged my code using Eclipse. The error I get is when the input is {1,2,3} and should return {1,3,2} -- it says my algorithm returns {1,2,3} instead.

    The main idea of my algorithm is to use these data structures' methods to easily retrieve the data I store in them in the order requested. I use a double length so I can use Math.ceil() to store the data in the correct order. If length is 3, Math.ceil(3/2) = 2, thus, it stores 1 and 2 in the LinkedList and 3 in the stack.

    If the length > 0, the first element would be from the LinkedList, therefor, the last part of the algorithm selects an item from the stack (if not empty) and then from the list (if not empty). This seems correct when debugged in my developing environment, but not in when submitted.

    I would appreciate some feedback and comments.

    Cheers.

    import java.util.*;
    
    public class Solution {
        public void reorderList(ListNode head) {
            
            Stack<Integer> S = new Stack<Integer>();
            LinkedList<Integer> L = new LinkedList<Integer>();
            
            double length = 0;
            boolean empty = true;
            ListNode temp = head;
            
            while(temp!=null) {
                length++;
                temp = temp.next;   
            }
            if(length>0) empty = false;
            
            temp = head;
            if(!empty) {
                for(int i=0; i < (int) Math.ceil(length/2); i++) {
                    L.addLast(temp.val);
                    temp = temp.next;
                }
                for(int i= (int) Math.ceil(length/2); i < length; i++) {
                    S.push(temp.val);
                    temp = temp.next;                  
                }
            }
            
            if(length>0) {
                head = new ListNode(L.removeFirst());
                length--;
            }
            
            temp = head;
            while(length > 0) {
                if(!S.empty()) {
                    temp.next = new ListNode(S.pop());
                    length--;
                    temp = temp.next;
                    if(!L.isEmpty()) {
                        temp.next = new ListNode(L.remove());
                        length--;
                        temp = temp.next;
                    }
                }
                else if(!L.isEmpty()) {
                    temp.next = new ListNode(L.remove());
                    length--;
                    temp = temp.next;
                    if(!S.empty()) {
                        temp.next = new ListNode(S.pop());
                        length--;
                        temp = temp.next;
                    }
    	        }
            }
        }
    }

  • 1
    S

    Looks like your code does manage to reorder the linked list, but it is not done in-place (i.e. you have created new copies of the nodes). Your code won't pass if the test code is written this way:

    head = ... // Create a linked list;
    temp = head; // Create an alias
    reorderList(temp); // The object that temp refers to is changed
    assert(compare(head, test_head)); // But head still refers to the original linked list, which is unaltered
    

    I don't know how Leetcode exactly codes the testing process, but it seems that it is something similar to what I described, since the following function:

    public void reorderList(ListNode head) {
        head = null;
        return;
    }
    

    would also report

    Input:  	{1,2,3}
    Output: 	{1,2,3}
    Expected: 	{1,3,2}
    

    So try to code up something that does modify the original linked list, or better yet, without the need of any other extra memory space such as a stack.


  • 0
    P

    Awesome, I will try to code up a solution with your suggestion. Thanks for your comment.


Log in to reply
 

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