【D37】K 个一组翻转链表&数据流的中位数 （LC 25&29

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

• 用栈来存储需要反转的链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    Deque<ListNode> stack = new LinkedList<>();

    public ListNode reverseKGroup(ListNode head, int k) {
        //添加虚拟头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        //反转链表的前驱结点pre
        ListNode pre = dummyHead, cur = head;

        while(cur != null){
            //1.将需要反转的一组结点入栈
            for(int i = 0 ; i < k && cur != null; i++){
                stack.push(cur);
                cur = cur.next;
            }

            //剩余结点不足k个，则直接结束循环
            if(stack.size() < k){
                break;
            }

            //反转链表的后继结点tail
            ListNode tail = cur,temp = pre;
            while(!stack.isEmpty()){
                temp.next = stack.pop();
                temp = temp.next;
            }
            //该组最后一个结点成为下一组结点的前驱结点
            pre = temp;
            //最后一个结点指向后继结点
            temp.next = tail;  
        }
        return dummyHead.next;
    }
}

295. 数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，[2,3,4] 的中位数是 3; [2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

• 维护一个升序的列表，每次插入时使用二分查找的方法寻找插入位置

class MedianFinder {

    ArrayList<Integer> list;
    /** initialize your data structure here. */
    public MedianFinder() {
        list = new ArrayList<>();
    }
    
    public void addNum(int num) {
        //二分查找插入位置   
        list.add(insertIndex(num), num);
    }

    private int insertIndex(int num){
        int left = 0, right = list.size() - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(list.get(mid) == num){
                return mid;
            }else if(list.get(mid) < num){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
    
    public double findMedian() {
        int len = list.size();
        double temp = (double)  list.get(len/2);
        if(list.size() % 2 == 0){
            temp = (temp + list.get(len/2 - 1)) / 2;
        }
        return temp;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */