本文解决的问题: 按主题归纳 链表 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
链表 【】,【】
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交**:**
题目数据 保证 整个链式结构中不存在环。
注意 ,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
**进阶:**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?
提示: listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点,intersectVal 为 0
如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]
示例:
1 2 3 4 5 6 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8' 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 — 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
1 2 3 4 5 输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2' 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
1 2 3 4 5 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出:No intersection 解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 public ListNode getIntersectionNode (ListNode headA, ListNode headB) { if (headA == null || headB == null ) { return null ; } ListNode a = headA, b = headB; while (a != null || b != null ) { if (a == b) { return a; } a = a == null ? headB : a.next; b = b == null ? headA : b.next; } return null ; } public ListNode getIntersectionNode (ListNode headA, ListNode headB) { ListNode aList = headA; ListNode bList = headB; while (aList != null && bList != null ) { aList = aList.next; bList = bList.next; } while (aList != null ) { headA = headA.next; aList = aList.next; } while (bList != null ) { headB = headB.next; bList = bList.next; } while (headA != headB) { headA = headA.next; headB = headB.next; } return headA; }
【递归】、【链表】
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
**进阶:**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
提示: 链表中节点的数目范围是 [0, 5000]
5000 <= Node.val <= 5000
示例:
1 2 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
1 2 输入:head = [1,2] 输出:[2,1]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public ListNode reverseList (ListNode head) { if (head == null || head.next == null ) { return head; } ListNode pre = new ListNode (head.val); while (head.next != null ) { ListNode current = new ListNode (head.next.val); head = head.next; current.next = pre; pre = current; } return pre; }
【栈】、【递归】、【链表】、【双指针】
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
提示: 链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
示例:
1 2 输入:head = [1,2,2,1] 输出:true
1 2 输入:head = [1,2] 输出:false
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public ListNode reverseList (ListNode head) { if (head == null || head.next == null ) { return head; } ListNode cur = head; ListNode pre = null ; while (cur != null ) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } public boolean isPalindrome (ListNode head) { if (head == null || head.next == null ) { return true ; } ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null ) { fast = fast.next.next; slow = slow.next; } ListNode listNode = reverseList(slow.next); while (listNode != null ) { if (listNode.val != head.val) { return false ; } listNode = listNode.next; head = head.next; } return true ; }
【递归】、【链表】、【数学】
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表
提示: 每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
示例:
1 2 3 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807
1 2 输入:l1 = [0], l2 = [0] 输出:[0]
1 2 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public ListNode addTwoNumbers (ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode (); ListNode current = dummyHead; int carry = 0 ; while (l1 != null || l2 != null || carry != 0 ) { int sum = carry; if (l1 != null ) { sum += l1.val; l1 = l1.next; } if (l2 != null ) { sum += l2.val; l2 = l2.next; } carry = sum / 10 ; current.next = new ListNode (sum % 10 ); current = current.next; } return dummyHead.next; }
【哈希表】、【链表】、【双指针】
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
**进阶:**你能用 O(1)(即,常量)内存解决此问题吗?
提示: 链表中节点的数目范围是 [0, 104]
105 <= Node.val <= 105
pos 为 1 或者链表中的一个 有效索引 。
示例:
1 2 3 输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
1 2 3 输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。
1 2 3 输入:head = [1], pos = -1 输出:false 解释:链表中没有环。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public boolean hasCycle (ListNode head) { if (head == null || head.next == null ) { return false ; } ListNode fast = head.next; ListNode slow = head; while (fast != slow) { if (fast == null || fast.next == null ) { return false ; } fast = fast.next.next; slow = slow.next; } return true ; }
【哈希表】、【链表】、【双指针】
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始 )。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递 ,仅仅是为了标识链表的实际情况。
不允许修改 链表。
**进阶:**你是否可以使用 O(1) 空间解决此题?
提示: 链表中节点的数目范围在范围 [0, 104] 内
105 <= Node.val <= 105
pos 的值为 1 或者链表中的一个有效索引
示例:
1 2 3 输入:head = [3,2,0,-4], pos = 1 输出:返回索引为 1 的链表节点 解释:链表中有一个环,其尾部连接到第二个节点。
1 2 3 输入:head = [1,2], pos = 0 输出:返回索引为 0 的链表节点 解释:链表中有一个环,其尾部连接到第一个节点。
1 2 3 输入:head = [1], pos = -1 输出:返回 null 解释:链表中没有环。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public ListNode detectCycle (ListNode head) { if (head == null || head.next == null ) { return null ; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null && slow.next != null ) { fast = fast.next.next; slow = slow.next; if (fast == slow) { ListNode pre = head; while (pre != slow) { pre = pre.next; slow = slow.next; } return pre; } } return null ; }
【递归】、【链表】
给你链表的头节点 head,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
**进阶:**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?
提示: 链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
示例:
1 2 输入:head = [1,2,3,4,5], k = 2 输出:[2,1,4,3,5]
1 2 输入:head = [1,2,3,4,5], k = 3 输出:[3,2,1,4,5]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 public ListNode reverseKGroup (ListNode head, int k) { if (head == null || k <= 1 ) { return head; } ListNode dummy = new ListNode (0 ); dummy.next = head; ListNode prevGroupEnd = dummy; while (true ) { ListNode kthNode = getKthNode(prevGroupEnd, k); if (kthNode == null ) { break ; } ListNode nextGroupStart = kthNode.next; ListNode[] reversedGroup = reverseList(prevGroupEnd.next, k); prevGroupEnd.next = reversedGroup[0 ]; prevGroupEnd = reversedGroup[1 ]; prevGroupEnd.next = nextGroupStart; } return dummy.next; } private ListNode getKthNode (ListNode start, int k) { while (start != null && --k >= 0 ) { start = start.next; } return start; } private ListNode[] reverseList(ListNode head, int k) { ListNode prev = null ; ListNode cur = head; ListNode next = null ; for (int i = 0 ; i < k; i++) { next = cur.next; cur.next = prev; prev = cur; cur = next; } return new ListNode [] {prev, head}; }
【链表】、【双指针】
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
**进阶:**你能尝试使用一趟扫描实现吗?
提示: 链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
示例:
1 2 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
1 2 输入:head = [1], n = 1 输出:[]
1 2 输入:head = [1,2], n = 1 输出:[1]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public ListNode removeNthFromEnd (ListNode head, int n) { ListNode dummy = new ListNode (0 , head); int length = getLength(head); ListNode cur = dummy; for (int i = 1 ; i < length - n + 1 ; ++i) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = dummy.next; return ans; } public int getLength (ListNode head) { int length = 0 ; while (head != null ) { ++length; head = head.next; } return length; }
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
提示: 链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
示例:
1 2 输入:head = [1,2,3,4] 输出:[2,1,4,3]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public ListNode swapPairs (ListNode head) { if (head == null || head.next == null ) { return head; } ListNode dumpNode1 = new ListNode (0 , head); ListNode dumpNode = dumpNode1; while (dumpNode.next != null && dumpNode.next.next != null ) { ListNode temp2 = dumpNode.next.next; ListNode temp1 = dumpNode.next; dumpNode.next = temp2; temp1.next = temp2.next; temp2.next = temp1; dumpNode = temp1; } return dumpNode1.next; }
【链表】、【分治】、【堆】、【归并排序】
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
提示: k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
示例:
1 2 3 4 5 6 7 8 9 10 输入: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
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 public ListNode mergeKLists (ListNode[] lists) { if (lists == null || lists.length == 0 ) { return null ; } return mergeKListsHelper(lists, 0 , lists.length - 1 ); } private ListNode mergeKListsHelper (ListNode[] lists, int start, int end) { if (start == end) { return lists[start]; } if (start > end) { return null ; } int mid = start + (end - start) / 2 ; ListNode left = mergeKListsHelper(lists, start, mid); ListNode right = mergeKListsHelper(lists, mid + 1 , end); return mergeTwoLists(left, right); } private ListNode mergeTwoLists (ListNode l1, ListNode l2) { ListNode dummy = new ListNode (0 ); ListNode current = dummy; while (l1 != null && l2 != null ) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null ) { current.next = l1; } else { current.next = l2; } return dummy.next; }
【链表】、【归并排序】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示: 两个链表的节点数目范围是 [0, 50]
100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
示例:
1 2 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public ListNode mergeTwoLists (ListNode l1, ListNode l2) { if (l1 == null ) { return l2; } else if (l2 == null ) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
【哈希表】、【链表】
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝 。深拷贝应该正好由 n 个全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
提示: 0 <= n <= 1000
104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
示例:
1 2 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
1 2 输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]]
1 2 输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public Node copyRandomList (Node head) { if (head == null ) { return null ; } Node current = head; while (current != null ) { Node newNode = new Node (current.val); newNode.next = current.next; current.next = newNode; current = newNode.next; } current = head; while (current != null ) { if (current.random != null ) { current.next.random = current.random.next; } current = current.next.next; } current = head; Node newHead = head.next; Node newCurrent = newHead; while (newCurrent.next != null ) { current.next = current.next.next; newCurrent.next = newCurrent.next.next; current = current.next; newCurrent = newCurrent.next; } current.next = null ; return newHead; }
【链表】、【双指针】、【分治】、【排序】、【归并排序】
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
**进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
提示: 链表中节点的数目在范围 [0, 5 * 104] 内
105 <= Node.val <= 105
示例:
1 2 输入:head = [4,2,1,3] 输出:[1,2,3,4]
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public ListNode sortList (ListNode head) { if (head == null || head.next == null ) { return head; } ListNode mid = findMiddle(head); ListNode rightHead = mid.next; mid.next = null ; ListNode left = sortList(head); ListNode right = sortList(rightHead); return merge(left, right); } private ListNode findMiddle (ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null ) { fast = fast.next.next; if (fast == null || fast.next == null ) { break ; } slow = slow.next; } return slow; } private ListNode merge (ListNode l1, ListNode l2) { ListNode dummy = new ListNode (0 ); ListNode cur = dummy; while (l1 != null && l2 != null ) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; }
请你设计并实现一个满足 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) 的平均时间复杂度运行。
提示: 1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 输入 ["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
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 public 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 ; } moveToHead(node); return node.value; } public void put (int key, int value) { DLinkedNode node = cache.get(key); if (node == null ) { 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 { 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; } }
参考资料