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();
*/
