Java solution using two pointer technique


  • 0
    W
    1. Move to the middle of the linked list using 'slow' and 'fast' pointers. Also keep a 'previous' pointer pointing to a node before 'slow'
    2. Add 'slow' value to BST
    3. To divide the list into two parts, make previous.next = null
    4. Call the same function with head node again
    5. Call the same function with slow.next

    Below is the code :-

    public class Solution {
        TreeNode root = null;
        public TreeNode sortedListToBST(ListNode head) {
            subListProcess(head);
            return root;
        }
        
        void subListProcess(ListNode head) {
            if(head == null)
                return;
            ListNode slow = head, fast = head, previous = null;
            while(fast != null && fast.next != null) {
                previous = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            root = insertInBST(slow.val, root);
            if(previous != null) {
                previous.next = null;
                subListProcess(head);
            }
            subListProcess(slow.next);
        }
        
        TreeNode insertInBST(int val, TreeNode root) {
            if(root == null)
                return new TreeNode(val);
            if(val < root.val)
                root.left = insertInBST(val, root.left);
            else
                root.right = insertInBST(val, root.right);
            return root;
        }
    }
    
    1. Time taken to get to the middle of the list : n/2, which is O(n)
    2. Above process is done logn time.
    3. To insert into BST, O(logn)

    So, overall, O(n(logn)^2). Please clarify if there is some mistake in time complexity calculation.


  • 1
    H

    I shrank your code and it's still easy to understand.

    public TreeNode sortedListToBST(ListNode head) {
        if(head==null){
            return null;
        }else if(head.next==null){
            return new TreeNode(head.val);
        }
        ListNode prev=null,cur=head,runner=head;
        while(runner!=null && runner.next!=null){
            prev=cur;
            cur=cur.next;
            runner=runner.next.next;
        }
        TreeNode root=new TreeNode(cur.val);
        if(prev!=null){
            prev.next=null;
            root.left=sortedListToBST(head);
        }
        root.right=sortedListToBST(cur.next);
        return root;
    }

Log in to reply
 

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