算法（十二）

1、对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上。

public class Solution {

    public int maxPoints(Point[] points) {

        if(points.length < 3 || points == null)

            return points.length;

        int output =0;

            for(int i=0;i<points.length-1;i++){

                int count = 0;

                long a = points[i].x;

                long b = points[i].y;

                long dx = a - points[i+1].x;

                long dy = b - points[i+1].y;

                if(dx==0 && dy==0){

                    for(int j=0;j<points.length;j++){

                        if(points[j].x==a && points[j].y==b){

                            count++;

                        }

                    }

                }else{

                    for(int j=0;j<points.length;j++){

                        if((points[j].x-a)*dy==(points[j].y-b)*dx){

                            count++;

                        }

                    }

                }

                output = Math.max(output,count);

            }

            return output;

 }

 }

2、在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
     
   public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode mid = getMid(head);
        ListNode midNext = mid.next;
        mid.next = null;
        return mergeSort(sortList(head), sortList(midNext));
    }
    private ListNode getMid(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, quick = head;
        while(quick.next != null && quick.next.next != null) {
            slow = slow.next;
            quick = quick.next.next;
        }
        return slow;
    }
    private ListNode mergeSort(ListNode n1, ListNode n2) {
        ListNode preHead = new ListNode(0);
        ListNode cur1 = n1;
        ListNode cur2 = n2;
        ListNode cur = preHead;
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if(cur1 != null){
            cur.next = cur1;
        }
        if(cur2 != null){
            cur.next = cur2;
        }
        return preHead.next;
    }
}