👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈
解法一
仿照两个升序链表合并一直循环 使用一个新节点res保存最终链表的头节点 然后循环遍历ListNode数组来与res来进行合并 时间复杂度
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
ListNode res = null;
for(ListNode t : lists){ // 遍历
ListNode newHead = new ListNode();
ListNode temp = newHead;
while(res != null && t !=null){ //合并
if(res.val < t.val){
temp.next = res;
res = res.next;
}else{
temp.next = t;
t = t.next;
}
temp = temp.next;
}
if(res != null) temp.next = res;
if(t != null)temp.next = t;
res = newHead.next;
}
return res;
}
}
解法二
使用归并排序 每两个链表进行合并后返回新链表的头节点 时间复杂度
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return div_list(lists,0,lists.length-1);
}
public ListNode div_list(ListNode[] lists,int left,int right){
if(left > right) return null;
if(left == right) return lists[left];
int mid = (right + left) / 2;
ListNode l = div_list(lists,left,mid);
ListNode r = div_list(lists,mid+1,right);
ListNode res = new ListNode();
ListNode t = res;
while(l != null && r != null){
if(l.val < r.val){
t.next = l;
l = l.next;
}else{
t.next = r;
r = r.next;
}
t =t.next;
}
if(l != null)t.next = l;
if(r != null)t.next = r;
return res.next;
}
}
解法一
先进行前序遍历保存节点 然后再重构
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
pre(root,list);
TreeNode r = list.get(0); // 获得第一个节点
for(TreeNode t:list){
if(t == r)continue;
r.left = null;
r.right = t;
r = t;
}
}
// 前序遍历结果
public void pre(TreeNode root,List<TreeNode> list){
if(root == null) return;
list.add(root);
pre(root.left,list);
pre(root.right,list);
}
}
解法二
将前序遍历与重构一起进行运行
注意:
由于递归的前序遍历不会保存孩子的信息,而我们修改过后会使树的结构混乱,所有我们需要提前保存孩子节点
class Solution {
TreeNode pre;
public void flatten(TreeNode root) {
if(root == null) return;
pre(root);
}
// 前序遍历结果
public void pre(TreeNode root){
if(root == null) return;
TreeNode l = root.left;
TreeNode r = root.right;
if(pre == null) pre = root; // 起始位置
else {
pre.left = null;
pre.right = root;
pre = root;
}
pre(l);
pre(r);
}
}
解法三
寻找前趋节点 我也是第一次见这个做法 首先这个节点如果没有左孩子,那么就只需要看右孩子 如果存在左孩子,就把右子树挂在左子树的最右边孩子的右边 然后把当前节点的右孩子设置为左孩子 当前节点的左孩子设置为null
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
TreeNode cur = root;
while(cur != null){
if(cur.left != null){
TreeNode left = cur.left; // 左子树的头节点
TreeNode t =left;
while(t.right != null){
t = t.right;
} // 循环过后 t 就是前序遍历左子树的最后一个遍历到的节点
t.right = cur.right;
cur.left = null;
cur.right = left;
}
cur = cur.right;
}
}
}
解法一
HashMap+双指针 因为get与put操作都要o(1) 所有使用HashMap来存储(key,node)
class LRUCache {
private Map<Integer,Node> cache = new HashMap<Integer,Node>();
private int size; //实际存放的大小
private int capacity; //最大存放大小
private Node tail,head; //头尾指针
public LRUCache(int capacity) {
this.capacity = capacity==0?16:capacity;
this.size = 0;
this.head = new Node();
this.tail = new Node();
head.ne = tail;
tail.pre = head;
}
public int get(int key) {
Node node = cache.get(key);
if(node == null) return -1;
deleteNode(node);
addToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if(node == null){ // 说明是新加入的节点
node = new Node(key,value);
if(size < capacity){ //说明是直接加入就行
addToHead(node);
size++;
}else if(size == capacity){
cache.remove(tail.pre.key);
deleteNode(tail.pre);
addToHead(node);
}
cache.put(key,node);
}else{ //说明key存在,需要修改value
deleteNode(node);
node.value = value;
addToHead(node);
}
}
public void addToHead(Node node){
Node ne = head.ne;
head.ne = node;
node.pre = head;
node.ne = ne;
ne.pre = node;
}
public void deleteNode(Node node){
node.pre.ne = node.ne;
node.ne.pre = node.pre;
// 垃圾回收
node.ne = null;
node.pre = null;
}
}
class Node{
int key; // key
int value; //value
Node pre; // 前一个节点
Node ne; // 后一个节点
public Node(){
}
public Node(int key,int value){
this.key = key;
this.value = value;
}
}