算法（十四）

1、1->8->5->4->6->3->2 以某个节点为分隔。要求所有比该节点小的都在该节点前，比该节点大的都在节点后但是相对位置不变如：x=4时，1->3->2->4->8->5->6。

public class test013 {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        ListNode p2 = head;
        int[] a = new int[]{1, 8, 5, 4, 6, 3, 2};
        int i=0;
        while(i<a.length){
            ListNode newHead = new ListNode(a[i]);
            p.next = newHead;
            p = p.next;
            i++;
        }

        while (p2.next != null){
            System.out.print(p2.next.val+" ");
            p2=p2.next;
        }

        ListNode res = fun(head, 4);
        System.out.println();
        System.out.println("根据规则得：");
        while (res.next!=null){
            System.out.print(res.next.val+" ");
            res = res.next;
        }
    }

    private static ListNode fun(ListNode head, int key) {
        ListNode p = head.next;
        ListNode p2 = head;
        ListNode head1 = new ListNode(0);
        ListNode ph1 = head1;
        ListNode head2 = new ListNode(0);
        ListNode ph2 = head2;
        while(p!=null){
            if(p.val < key){
                ph1.next = p;
                ph1 = ph1.next;
                p = p.next;
                ph1.next = null;
            }else if(p.val > key){
                ph2.next = p;
                ph2 = ph2.next;
                p = p.next;
                ph2.next = null;
            }else{
                p = p.next;
            }
        }
        System.out.println();
        System.out.println("head1链表的值如下：");
        while(head1.next!=null){
            System.out.print(head1.next.val+" ");
            p2.next = head1.next;
            p2 = p2.next;
            head1 = head1.next;
        }
        System.out.println();
        p2.next = new ListNode(key);
        p2 = p2.next;
        System.out.println("head2链表的值如下：");
        while(head2.next!=null){
            System.out.print(head2.next.val+" ");
            p2.next = head2.next;
            p2 = p2.next;
            head2 = head2.next;
        }
        return head;
    }
}

2、给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Interval {
    int start;
    int end;

    public Interval(){
        start =0;
        end =0;
    }
    public Interval(int s, int e) {
        start = s;
        end = e;
    }
}
public class test015 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int i=0;
        ArrayList<Interval> list = new ArrayList<>();
        while (i<N){
            int s = sc.nextInt();
            int e = sc.nextInt();
            Interval interval = new Interval(s, e);
            list.add(interval);
            i++;
        }
        ArrayList<Interval> res = merge(list);
    }
    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        int n=intervals.size();
        int[] starts=new int[n];
        int[] ends=new int[n];
        for(int i=0;i<n;i++){
            starts[i]=intervals.get(i).start;
            ends[i]=intervals.get(i).end;
        }
        System.out.println("排序前：");
        for(int i=0; i<n; i++){
            System.out.print(starts[i]+" ");
            System.out.print(ends[i]);
            System.out.println();
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        System.out.println("排序后：");
        for(int i=0; i<n; i++){
            System.out.print(starts[i]+" ");
            System.out.print(ends[i]);
            System.out.println();
        }
        System.out.println("合并区间后：");
        ArrayList<Interval> res=new ArrayList<Interval>();
        for(int i=0,j=0;i<n;i++){
            if(i==n-1||starts[i+1]>ends[i]){
                System.out.print(starts[j]+" ");
                System.out.println(ends[i]);
                res.add(new Interval(starts[j],ends[i]));
                j=i+1;
            }
        }
        return res;
    }
}