Vivek
BAN USERThe below is a java program to merge sort a linked list. It works!
time complexity - O(n logn)
space complexity - O(1)
class MergeSortForLinkedList{
private static int linkedListLength;
private static LinkedListNode mainList;
//this method needs to be called to merge the linked list
public static LinkedListNode mergeSort(LinkedListNode list){
if(list == null)
return null;
linkedListLength = findListLength(list); //finds length of linked list
mainList = list;
return mergeSort(0, linkedListLength-1);
}
private static LinkedListNode mergeSort(int start, int end){
if(start == end){
LinkedListNode x = mainList;
mainList = mainList.nextNode;
x.nextNode = null;
return x;
}
int mid = (start+end)/2;
LinkedListNode left = mergeSort(start,mid);
LinkedListNode right = mergeSort(mid+1, end);
LinkedListNode toReturn = merge(left, right);
return toReturn;
}
//merges two null ended linked lists in natural order and returns the head of the resultant list
private static LinkedListNode merge(LinkedListNode list1, LinkedListNode list2){
if(list1 == null)
return list2;
if(list2 == null)
return list1;
LinkedListNode head;
if( list1.data <= list2.data ){
head = list1;
list1 = list1.nextNode;
}
else{
head = list2;
list2 = list2.nextNode;
}
LinkedListNode tail = head;
while(list1 != null && list2!=null){
if( list1.data <= list2.data){
tail.nextNode = list1;
tail = list1;
list1 = list1.nextNode;
}
else{
tail.nextNode = list2;
tail = list2;
list2 = list2.nextNode;
}
}
if(list1 == null && list2 == null)
return head;
if(list1 == null){
tail.nextNode = list2;
return head;
}
if(list2 == null){
tail.nextNode = list1;
return head;
}
return null;
}
private static int findListLength(LinkedListNode head){
if(head == null)
return 0;
int length = 0;
while(head != null){
length++;
head = head.nextNode;
}
return length;
}
public static void printLinkedList(LinkedListNode head){
if(head == null)
return;
while(head != null){
System.out.print(head.data+" ");
head = head.nextNode;
}
System.out.println();
return;
}
public static void main(String[] args){
LinkedListNode node1 = new LinkedListNode(3, null);
LinkedListNode head = node1;
LinkedListNode node2 = new LinkedListNode(5, null);
node1.nextNode = node2;
node1 = new LinkedListNode(1, null);
node2.nextNode = node1;
node2 = new LinkedListNode(2, null);
node1.nextNode = node2;
node1 = new LinkedListNode(0, null);
node2.nextNode = node1;
node2 = new LinkedListNode(3, null);
node1.nextNode = node2;
node1 = new LinkedListNode(7, null);
node2.nextNode = node1;
node2 = new LinkedListNode(8, null);
node1.nextNode = node2;
printLinkedList(head);
LinkedListNode sortedListHead = mergeSort(head);
printLinkedList(sortedListHead);
return;
}
}
Output:
new-users-macbook:Interviews newuser$ java MergeSortForLinkedList
3 5 1 2 0 3 7 8
0 1 2 3 3 5 7 8
great solution.
the only change need to be done is we need to do the conversion from doubly linked list to BST in place. That is, we must change previous and next pointers of a double linked list node in such a way that they hold left and right subtrees of a BST. So each double linked list node actually becomes a BST tree node in place.
below is the code in Java with that small change:
private static int lengthOfDLL;
private static DoubleLinkedListNode currentNode;
public static DoubleLinkedListNode convertDLLToBST(DoubleLinkedListNode dll){
if(dll == null)
return null;
lengthOfDLL = findDLLLength(dll);
currentNode = dll;
return convertDLLToBST( 0, lengthOfDLL-1);
}
private static DoubleLinkedListNode convertDLLToBST(int start, int end){
if( start > end)
return null;
int mid = (start+end) / 2;
DoubleLinkedListNode nodeLeft = convertDLLToBST( start, mid-1);
currentNode.previous = nodeLeft;
DoubleLinkedListNode thisNode = currentNode;
currentNode = currentNode.next;
DoubleLinkedListNode nodeRight = convertDLLToBST( mid+1 , end);
thisNode.next = nodeRight;
return thisNode;
}
So, after conversion, previous holds pointer to left subtree, next holds pointer to right sub tree
I think I have an O(n^2) soution.
There are n points.
1) consider n^2 combination of two points. calculate the slope of the pair of points and put the slope vs list of pair of points in a hashmap
ex. HashMap<Slope (double), ArrayList<Pair of points>>
2) so all the maximum number of points that fall on the same line should be in the same slope-arraylist map entry
3) For every map entry's list of points - check how many points fall on the same line using the line equation
- Vivek July 18, 2012