秋招-数据结构-链表篇
介绍
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
技巧
可以使用快慢指针来解决一些循环、遍历等问题,也可以借助PriorityQueue优先级队列,最小堆等其他结构,用空间换时间。
例题
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode more,less,te_more,te_less;
te_more = more = new ListNode();
te_less = less = new ListNode();
while(head!=null){
if(head.val<x){
less.next = new ListNode(head.val);
less = less.next;
}else{
more.next = new ListNode(head.val);
more = more.next;
}
head = head.next;
}
less.next = te_more.next;
return te_less.next;
}
}
每次取lists里面的每个头结点,找最小的构建新链表,这个找最小的可以用PriorityQueue来解决
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列,最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点,接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
}