4 ms·
You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution. You could even do this in place wi
by tzs 9y ago
You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution.
You could even do this in place without increasing the size of each node at the cost of doubling the size of variables that point to nodes and slightly lowing down stepping through the list. You do this by storing the next and previous pointers for each node in the same location, xor'ed together.
That doubles the size of variables that point to nodes and slows down stepping because you have to turn them into structs that store both a pointer to the node and a pointer to an adjacent node and update both of these pointers as you move through the list.
- jandrese 9y agoIf you're willing to burn O(n) memory on it you could just create an array of pointers to the nodes in the list and then use that to build the balanced tree. It's probably faster than iterating over the sublist every time to find the center. This assumes of course that the list is sorted. If not, you should probably sort the list first to avoid driving yourself insane. If memory is too tight to make temporary storage and the list is too big to sort and you want a perfectly balanced tree then you've got an interesting problem on your hands.
- pklausler 9y agoYou can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space. EDIT: demonstration: sortList [] = [] sortList [x] = [x] sortList xs = merge (sortList as) (sortList bs) where (as, bs) = split xs split [] = ([], []) split [x] = ([x], []) split (x:y:rest) = let (xs, ys) = split rest in (x:xs, y:ys) merge xs [] = xs merge [] ys = ys merge (x:xs') ys@(y:_) | x <= y = x : merge xs' ys merge xs (y:ys) = y : merge xs ys data Tree a = Empty | Node a (Tree a) (Tree a) deriving(Show) balancedTree xs = mktree (length xs) xs where mktree 0 [] = Empty mktree n xs = Node x (mktree n' less) (mktree (n - 1 - n') more) where n' = (n - 1) `div` 2 (less, (x:more)) = splitAt n' xs listToBalancedTree :: Ord a => [a] -> Tree a listToBalancedTree = balancedTree . sortList