25. K 個(gè)一組翻轉(zhuǎn)鏈表
給你一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)狈蚤，請(qǐng)你返回翻轉(zhuǎn)后的鏈表孝赫。
k 是一個(gè)正整數(shù)互艾，它的值小于或等于鏈表的長度社露。
如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序店读。
- 用棧來存儲(chǔ)需要反轉(zhuǎn)的鏈表
/**
* 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) {
//添加虛擬頭節(jié)點(diǎn)
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
//反轉(zhuǎn)鏈表的前驅(qū)結(jié)點(diǎn)pre
ListNode pre = dummyHead, cur = head;
while(cur != null){
//1.將需要反轉(zhuǎn)的一組結(jié)點(diǎn)入棧
for(int i = 0 ; i < k && cur != null; i++){
stack.push(cur);
cur = cur.next;
}
//剩余結(jié)點(diǎn)不足k個(gè)嗦枢，則直接結(jié)束循環(huán)
if(stack.size() < k){
break;
}
//反轉(zhuǎn)鏈表的后繼結(jié)點(diǎn)tail
ListNode tail = cur,temp = pre;
while(!stack.isEmpty()){
temp.next = stack.pop();
temp = temp.next;
}
//該組最后一個(gè)結(jié)點(diǎn)成為下一組結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
pre = temp;
//最后一個(gè)結(jié)點(diǎn)指向后繼結(jié)點(diǎn)
temp.next = tail;
}
return dummyHead.next;
}
}
295. 數(shù)據(jù)流的中位數(shù)
中位數(shù)是有序列表中間的數(shù)。如果列表長度是偶數(shù)屯断，中位數(shù)則是中間兩個(gè)數(shù)的平均值文虏。
例如，[2,3,4] 的中位數(shù)是 3; [2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5
設(shè)計(jì)一個(gè)支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：
void addNum(int num) - 從數(shù)據(jù)流中添加一個(gè)整數(shù)到數(shù)據(jù)結(jié)構(gòu)中殖演。
double findMedian() - 返回目前所有元素的中位數(shù)氧秘。
- 維護(hù)一個(gè)升序的列表，每次插入時(shí)使用二分查找的方法尋找插入位置
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();
*/
