链表
移除链表元素
删除链表中等于给定值val的所有节点。
设置一个虚拟头节点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
ListNode dummy = new ListNode(-1,head);
ListNode cur = head;
ListNode pre = dummy;
while(cur != null) {
if(cur.val == val) {
pre.next = cur.next;
}else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
反转链表
反转一个单链表。
只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表。
public ListNode reverseList(ListNode head) {
if(head == null) return head;
ListNode cur = head;
ListNode pre = null;
ListNode temp = null;
while(cur != null) {
temp = cur.next; //保存下一个节点
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
递归法：
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
public ListNode reverse(ListNode pre,ListNode cur) {
if(cur == null) {
return pre;
}
ListNode temp = cur.next;
cur.next = pre;
return reverse(cur,temp);
}
反转链表II
给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置left到位置right的链表节点，返回反转后的链表。
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
头插法反转链表：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。
使用三个指针变量pre、head、nex来记录反转的过程中需要的变量：
- head：指向待反转区域的第一个节点left；
- nex：永远指向head的下一个节点，循环过程中，head变化以后nex也会变化；
- pre：永远指向待反转区域的第一个节点left的前一个节点，在循环过程中不变。
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0,head);
ListNode pre = dummy;
for(int i = 1;i < left;i++) {
pre = pre.next;
}
head = pre.next;
for(int i = left; i < right;i++) {
ListNode nex = head.next;
head.next = nex.next;
nex.next = pre.next;
pre.next = nex;
}
return dummy.next;
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
while(pre.next != null && pre.next.next != null) {
ListNode temp = head.next.next;
pre.next = head.next;
head.next.next = head;
head.next = temp;
pre = head;
head = head.next;
}
return dummy.next;
}
递归法：
public ListNode swapPairs(ListNode head) {
// base case 退出提交
if(head == null || head.next == null) return head;
// 获取当前节点的下一个节点
ListNode next = head.next;
// 进行递归
ListNode newNode = swapPairs(next.next);
// 这里进行交换
next.next = head;
head.next = newNode;
return next;
}
删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第n个节点，并且返回链表的头节点。
双指针的经典应用，采用虚拟头节点的方式，fast和slow指针都指向虚拟头节点。如果要删除倒数第n个节点，让fast移动n+1步，然后fast和slow指针一起移动，直到fast指针指向null，这时slow会指向待删除节点的前一个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null) return head;
ListNode dummy = new ListNode(-1,head);
ListNode fast = dummy;
ListNode slow = dummy;
//先放fast移动n+1个位置
for(int i = 0; i < n + 1; i++) {
fast = fast.next;
}
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
链表相交
给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始位置。如果两个单链表没有交点，返回null。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != null) {
lenA++;
curA = curA.next;
}
while(curB != null) {
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
//总是让curA为最长链表的头，lenA为其长度
if(lenB > lenA) {
ListNode temp = curA;
curA = curB;
curB = temp;
int tempLen = lenA;
lenA = lenB;
lenB = tempLen;
}
int offset = lenA - lenB;
while(offset > 0) {
curA = curA.next;
offset--;
}
while(curA != null) {
if(curA == curB) { //审题重点：交点不是数值相等而是指针相等
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
需要注意的是，交点不是数值相等，而是指针相等。
复杂链表的复制
请实现copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
利用哈希表的查询特点，考虑构建原链表节点和新链表对应节点的键值对映射关系，再遍历构建新链表各节点的next和random引用指向即可。
- 若头节点head为空节点，直接返回null
- 初始化：哈希表dic，节点cur指向头结点
- 复制链表：建立新节点，并向dic添加键值对(原cur节点，新cur节点); cur遍历至原链表下一节点
- 构建新链表的引用指向：构建新节点的next和random引用指向
- 返回值：新链表的头结点dic[cur];
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map<Node,Node> map = new HashMap<>();
while(cur != null) {
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字0之外，这两个数都不会以0开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。如果当前两个链表处相应位置的数字位n1,n2，进位值位carry，则它们的和为n1 + n2 + carry；其中答案链表处相应位置的数字为(n1 + n2 + carry) mod 10，而新的进位值为(n1 + n2 + carry) / 10。如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个0。此外，如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为carry。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while(l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if(head == null) {
head = tail = new ListNode(sum % 10);
}else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
if(carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
输入：head = [1,2,2,1]
输出：true
输入：head = [1,2]
输出：false
将值复制到数组后用双指针法：
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
while(head != null) {
list.add(head.val);
head = head.next;
}
int left = 0, right = list.size() - 1;
while(left <= right) {
if(list.get(left) == list.get(right)) {
left++;
right--;
}else {
return false;
}
}
return true;
}
排序链表
给你链表的头结点head，请将其按升序排列并返回排序后的链表。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
对链表自顶向下归并排序的过程如下：
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动2步，慢指针每次移动1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于1，即当链表为空或者链表只包含1个节点时，不需要对链表进行拆分和排序。
public ListNode sortList(ListNode head) {
//归并排序链表
return sortList(head,null);
}
public ListNode sortList(ListNode head,ListNode tail) {
if(head == tail) return head;
if(head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while(fast != tail) {
slow = slow.next;
fast = fast.next;
if(fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = sortList(head,mid);
ListNode list2 = sortList(mid,tail);
ListNode sorted = merge(list1,list2);
return sorted;
}
public ListNode merge(ListNode head1,ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead,temp1 = head1,temp2 = head2;
while(temp1 != null && temp2 != null) {
if(temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
}else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if(temp1 != null) {
temp.next = temp1;
}else if(temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
旋转链表
给你一个链表的头结点head，旋转链表，将链表每个节点向右移动k个位置。
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
输入：head = [0,1,2], k = 4
输出：[2,0,1]
首先计算出链表的长度n，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表。然后找到新链表的最后一个节点(即原链表的第(n-1) - (k mod n)个节点(从0开始计数)，将当前闭合为环的链表在找到的最后一个节点后断开，并记录下最后一个节点的后一个节点，即可得到所需要的结果。
特别地，当链表长度不大于1，或者k为n的倍数时，新链表将与原链表相同，无需进行任何处理。
public ListNode rotateRight(ListNode head, int k) {
if(k == 0 || head == null || head.next == null) return head;
int count = 1;
ListNode cur = head;
while(cur.next != null) {
cur = cur.next;
count++;
}
//找到旋转链表的最后一个元素
int lastNum = count - k % count;
//最后一个元素为原始位置 则无需进行旋转
if(lastNum == count) return head;
cur.next = head;
while(lastNum-- > 0) {
cur = cur.next;
}
ListNode result = cur.next;
cur.next = null;
return result;
}
分隔链表
给你一个头节点为head的单链表和一个整数，请你设计一个算法将链表分割为k个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过1。这可能导致有些部分为null。这k个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。返回由上述k部分组成的数组。
输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
题目要求将给定的链表分隔成k个连续的部分。由于分隔成的每个部分的长度和原始链表的长度有关，因此需要首先遍历链表，得到链表的长度n。得到链表的长度n之后，记quotient = n / k，remainder = n mod k，则在分隔成的k个部分中，前remainder个部分的长度各为quotient + 1，其余每个部分的长度各为quotient。
分隔链表时，从链表的头节点开始遍历，记当前节点为curr，对于每个部分，进行如下操作：
- 将curr作为当前部分的头节点；
- 计算当前部分的长度partSize；
- 将curr向后移动partSize步，则curr为当前部分的尾节点；
- 当curr到达当前部分的尾节点时，需要拆分curr和后面一个节点之间的连接关系，在拆分之前需要存储curr的后一个节点next；
- 令curr的next指针指向null，完成curr和next的拆分；
- 将next赋值给curr。
完成上述操作之后，即得到分隔链表后的一个部分。重复上述操作，直到分隔出k个部分，或者链表遍历结束，即curr指向null。
public ListNode[] splitListToParts(ListNode head, int k) {
int count = 0;
ListNode temp = head;
while(temp != null) {
count++;
temp = temp.next;
}
int quotient = count / k, remainder = count % k;
ListNode[] parts = new ListNode[k];
ListNode cur = head;
for(int i = 0; i < k && cur != null; i++) {
parts[i] = cur;
int partSize = quotient + (i < remainder ? 1 : 0);
for(int j = 1; j < partSize; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return parts;
}
扁平化多级双向链表
你会得到一个双链表，其中包含的节点有一个下一个指针、前一个指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点
给定链表的头节点head，将链表扁平化，以便所有节点都出现在单层双链表中。让curr是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的curr之后和curr.next之前。返回扁平列表的head。列表中的节点必须将其所有子指针设置为null。
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：输入的多级列表如上图所示。 扁平化后的链表如下图：
深度优先搜索
当遍历到某个节点node时，如果它的child成员不为空，那么需要将child指向的链表结构进行扁平化，并且插入node与node的下一个节点之间。因此，当遇到child成员不为空节点时，就要先去处理child指向的链表结构，这就是一个深度优先搜索的过程。当完成了对child指向的链表结构的扁平化之后，就可以回溯到node节点。为了能够将扁平化的链表插入node与node的下一个节点之间，我们需要知道扁平化的链表的最后一个节点last，随后进行如下的三步操作：
- 将node与node的下一个节点next断开
- 将node与child相连
- 将last与next相连
需要注意的时，node可能没有下一个节点，即next为空。此时，我们只需进行第二步操作。此外，在插入扁平化的链表后，需要将node的child成员置为空。
public Node flatten(Node head) {
dfs(head);
return head;
}
public Node dfs(Node node) {
Node cur = node;
//记录链表的最后一个节点
Node last = null;
while(cur != null) {
Node next = cur.next;
//如果有子节点，那么首先处理子节点
if(cur.child != null) {
Node childLast = dfs(cur.child);
//将node与child相连
cur.next = cur.child;
cur.child.prev = cur;
//如果next不为空，就将last与next相连
if(next != null) {
childLast.next = next;
next.prev = childLast;
}
//将child置空
cur.child = null;
last = childLast;
}else {
last = cur;
}
cur = next;
}
return last;
}
排序的循环链表
给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素insertVal，使这个列表仍然是循环升序的。给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。如果列表为空，需要创建一个循环有序列表并返回这个节点。否则，请返回原先给定的节点。
输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。
输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。
输入：head = [1], insertVal = 0
输出：[1,0]
如果循环链表为空，则插入一个新节点并将新节点的next指针指向自身，插入新节点之后得到只有一个节点的循环链表，该循环链表一定是有序的，将插入的新节点作为新的头节点返回。
如果循环链表的头节点的next指针指向自身，则循环链表中只有一个节点，在头节点之后插入新节点，将头节点的next指针指向新节点，将新节点的next指针指向头节点，此时循环链表中有两个节点且一定是有序的，返回头节点。
如果循环链表的节点数大于1，则需要从头结点开始遍历循环链表，寻找插入新节点的位置，使得插入新节点之后的循环链表仍然保持有序。
用curr和next分别表示当前节点和下一个节点，初始时curr位于head，next位于head的下一个节点，由于链表中的节点数大于1，因此curr != next。遍历过程中，判断值为insertVal的新节点是否可以在curr和next之间插入，如果符合插入要求则在curr和next之间插入新节点，否则将curr和next同时向后移动，直到找到插入新节点的位置或者遍历完循环链表中的所有节点。
遍历过程中，如果找到插入新节点的位置，则有以下三种情况：
- curr.cal <= insertVal <= next.val，此时新节点的值介于循环链表中的两个节点值之间，在curr和next之间插入新节点。
- curr.val > next.val且insertVal > curr.val，此时curr和next分别是循环链表中值最大的节点和值最小的节点，insertVal大于curr的节点值，因此新节点应该在curr的后面插入，即在curr和next之间插入新节点。
- curr.val > next.val且insertVal < next.val，此时curr和next分别是循环链表中值最大的节点和值最小的节点，insertVal小于next的节点值，因此新节点应该在next的前面插入，即在curr和next之间插入新节点。
如果遍历完循环链表中的所有节点之后仍然没有遇到上述三种情况，则循环链表中的所有节点值都相同，因此新节点插入循环链表中的任何位置仍可以使循环链表保持有序，此时仍可在curr和next之间插入新节点。
public Node insert(Node head, int insertVal) {
Node node = new Node(insertVal);
if(head == null) {
node.next = node;
return node;
}
if(head.next == head) {
head.next = node;
node.next = head;
return head;
}
Node curr = head, next = head.next;
while(next != head) {
if(insertVal >= curr.val && insertVal <= next.val) {
break;
}
if(curr.val > next.val) {
if(insertVal > curr.val || insertVal < next.val) {
break;
}
}
curr = curr.next;
next = next.next;
}
curr.next = node;
node.next = next;
return head;
}
奇偶链表
给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。
原始链表的头节点head也是奇数链表的头节点以及结果链表的头节点，head的后一个节点是偶数链表的头节点。令evenHead = head.next，则evenHead是偶数链表的头节点。
维护两个指针odd和even分别指向奇数节点和偶数节点，初始时odd=head，even=evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。
- 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此odd.next = even.next，然后令odd = odd.next，此时odd变成even的后一个节点。
- 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此even.next = odd.next，然后令even = even.next，此时even变成odd的后一个节点。
在上述操作之后，即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完毕。全部节点分离完毕的条件是even为空节点或者even.next为空节点，此时odd指向最后一个奇数节点（即奇数链表的最后一个节点）。最后odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然时head。
public ListNode oddEvenList(ListNode head) {
if(head == null) return head;
ListNode evenHead = head.next;
ListNode odd = head, even = evenHead;
while(even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
LRU缓存
请你设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构。实现LRUCache类：
- LRUCache(int capacity)以正整数作为容量capacity初始化LRU缓存
- int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
- void put(int key,int value)如果关键字key已经存在，则变更数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。
函数get和put必须以O(1)的平均时间复杂度运行。
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
LRU缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射(HashMap)，通过缓存数据的键映射到其在双向链表中的位置。
首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1)的时间内完成get或者put操作。具体的方法如下：
- 对于get操作，首先判断key是否存在：
- 如果key不存在，则返回-1；
- 如果key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 对于put操作，首先判断key是否存在：
- 如果key不存在，使用key和value创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部。
在双向链表的实现中，使用一个伪头部和伪尾部标记界限，这样在添加和删除节点的时候就不需要检查相邻的节点是否存在。
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key,int _value) {
key = _key;
value = _value;
}
}
private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head,tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
//使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if(node == null) return -1;
//如果key存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
//如果key不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key,value);
//添加进哈希表
cache.put(key,newNode);
//添加至双向链表的头部
addToHead(newNode);
++size;
if(size > capacity) {
//如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
//删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
}else {
//如果key存在，先通过哈希表定位，再修改value，并移到头部
node.value = value;
moveToHead(node);
}
}
//往头部增加节点
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
//移除节点
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
//将已存在的节点移动到头部
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
//移除尾部节点
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
public ListNode mergeKLists(ListNode[] lists) {
//左闭右闭区间
return merge(lists,0,lists.length - 1);
}
//分治合并
public ListNode merge(ListNode[] lists, int left, int right) {
if(left == right) return lists[left];
if(left > right) return null;
int mid = (left + right) >> 1;
return mergeTwoLists(merge(lists,left,mid), merge(lists,mid + 1,right));
}
//两个链表的合并
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if(a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a,bPtr = b;
while(aPtr != null && bPtr != null) {
if(aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
}else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
投递地平线等公司7个岗位