Menu
Given a linked list of integers in random order, split it into two new linked lists such that the difference in the sum of elements of each list is maximal and the length of the lists differs by no more than 1 (in the case that the original list has an odd number of elements). I can't assume that the numbers in the list are unique.
The algorithm I thought of was to do a merge sort on the original linked list (O(n·log n) time, O(n) space ) and then use a recursive function to walk to the end of the list to determine its length, doing the splitting while the recursive function is unwinding. The recursive function is O(n) time and O(n) space.
Is this the optimal solution? I can post my code if someone thinks it's relevant.
489
1) Store the mid and last pointers of the circular linked list using tortoise and hare algorithm. 2) Make the second half circular. 3) Make the first half circular. 4) Set head (or start) pointers of the two linked lists.
Algorithm (Smallest element)Create a variable min and initialize it with INT_MAX. Traverse through the list and for every node, compare its data with min. If the current node's data is lesser than min, then store the value of the current node's data in min. In the end, min will contain the largest element of the list.
Split Linked List in Parts - LeetCode. Given the head of a singly linked list and an integer k , split the linked list into k consecutive linked list parts. The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.
No it's not optimal; you can find the median of a list in O(n), then put half of them in one list (smaller than median or equal, upto list size be n/2) and half of them in another list ((n+1)/2). Their sum difference is maximized, and there is no need to sort (O(n·log(n)). All things will be done in O(n) (space and time).
136
Why do you need recursive function? While sorting list, you can count it elements. Then just split it in half. This drops O(n) space requirement.
Even if you can't count list length while sorting, it still can be split in O(n) time and O(1) space: get two list iterators on the beginning, advance first 2 elements at each step, second 1 element each step. When first reaches list end - cut at second.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
