Sort a linked list in O(n log n) time using constant space complexity.

This one is easy. Merge sort can solve this problem.

See the following code for the merge sort from bottom to top

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *loop_list(ListNode *head, int len){
        // There are len nodes from head(inclusive) to ret(exclusive)
        while(head != NULL && len-- > 0) head = head -> next;
        return head;
    }
   
    ListNode *merge(ListNode *head, int len){
        // Merge len nodes beginning from head->next(inclusive), and return the last node.
        if(head == NULL || head -> next == NULL) return NULL;
       
        ListNode *a_beg = head -> next;
        ListNode *a_end = loop_list(a_beg, len/2 - 1);
        if(!a_end) return NULL;
       
        ListNode *b_beg = a_end -> next;
        a_end -> next = NULL;
       
        ListNode *b_end = loop_list(b_beg, len/2 - 1);
        ListNode *new_end = b_end == NULL ? NULL : b_end -> next;
        if(b_end != NULL) b_end -> next = NULL;
       
        ListNode *loop = head;
        ListNode *a_loop = a_beg;
        ListNode *b_loop = b_beg;
        while(a_loop || b_loop){
            ListNode *next;
            if(!a_loop) {
                next = b_loop;
            }
            else if(!b_loop){
                next = a_loop;
            }
            else next = (a_loop -> val < b_loop -> val) ? a_loop : b_loop;
            loop -> next = next;
            loop = loop -> next;
           
            if(next == a_loop){
                a_loop = a_loop -> next;
            }
            else if(next == b_loop){
                b_loop = b_loop -> next;
            }
        }
        loop -> next = new_end;
        return loop;
    }
   
    ListNode *sortList(ListNode *head) {
        ListNode *fake_head = new ListNode(0);
        fake_head -> next = head;
        int num_merge = 0;
        for(int len = 2; true; len *= 2){
            num_merge = 0;
            ListNode *loop = fake_head;
            while(loop && loop->next){
                loop = merge(loop, len);
                num_merge ++;
            }
            if(num_merge <= 1) break;
        }
        head = fake_head -> next;
        delete fake_head;
        return head;
    }
};

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

The following is a O(n^2 lg n) algorithm because I use TreeMap instead of HashMap.

 If I use HashMap, then the run time is O(n^2). But I did not find a way doing better than O(n^2).

Another question is that to use HashMap in java I need to define my own equals() and hashcode() functions, which is quite annoying. Especially hashcode() function, any one have a idea how to produce a good hashcode() function for this?


/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
import java.util.*;

class Slope implements Comparable<Slope>{
  int x;
  int y;
  Slope(int a, int b){
      if(b<0){
          a *= -1;
          b *= -1;
      }
      x = a; y = b;
  }
  public int compareTo(Slope other){
      return this.x * other.y - this.y * other.x;
  }
}

public class Solution {
    int numPointsCentered(Point[] points, int id){
        Map<Slope, Integer> counts = new TreeMap<Slope, Integer>();
        int num_same_point = 0;
        int return_max = 1;
        for(int i = 0; i < points.length; i++){
            if (i==id) continue;
            if (points[i].x==points[id].x && points[i].y==points[id].y){
                num_same_point++;
                continue;
            }
            Slope slope = new Slope(points[i].x - points[id].x, points[i].y - points[id].y);
            if(counts.containsKey(slope)){
                counts.put(slope, counts.get(slope) + 1);
            }else{
                counts.put(slope, 2);
            }
            return_max = Math.max(return_max, counts.get(slope));
        }
        return return_max + num_same_point;
    }
   
    public int maxPoints(Point[] points) {
        int num_points = 0;
        for(int i = 0; i < points.length; i++){
            int new_center_points = numPointsCentered(points, i);
            num_points = Math.max(num_points, new_center_points);
        }
        return num_points;
    }
}