Why is using 2 while loops so much slower?


  • 0

    So my solution is as follows:

    '''

    public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return head;

        ListNode first = head;
        ListNode second = head.next;
        
        
        while (head != null) {
            
            while (second != null && second.val == head.val) {
                second = second.next;
            }
            head.next = second;
            head = head.next;
        }
        return first;
        
    }
    

    '''

    Why is much solution 2ms compared to other solutions? Isn't the time complexity O(n)?


  • 0
    V

    Hello!
    Yes, it has to be O(n), even if you use two while loops.

    But, why use two loops, when you could do the same with one? I've provided the solution bellow with one while loop, which is based upon the same idea as yours with two while loops.

    Look here:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if(head==null||head.next==null)
                return head;
            ListNode node=head.next;
            ListNode previous=head;
            while(node!=null){
                if(node.val==previous.val)
                    node=previous.next=node.next;
                else
                    previous=previous.next;
            }
            return head;
        }
    

    Also, I couldn't restrained myself from writing recursive solution.
    So, recursive approach takes the same time as solutions above - O(n)
    Here is the code:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if(head==null||head.next==null)
                return head;
            else if(head.val==head.next.val)
                return deleteDuplicates(head.next);
            head.next=deleteDuplicates(head.next);
            return head;
        }
    }
    
    

    I hope you'll find it useful!


Log in to reply
 

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