hot100之链表下
<h3 id="k个一组翻转链表025">K个一组翻转链表(025)</h3><p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1, head);
ListNode prev = dummy;
while(prev.next != null){
ListNode curr = reverse(prev, k);
if (curr == null){
reverse(prev, k);
break;
}
prev = curr;
}
return dummy.next;
}
private ListNode reverse(ListNode prev, int k){
ListNode curr = prev.next;
int i = 1;
for (;i < k && curr.next != null; i++){
ListNode next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return i < k ? null : curr;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>重点在 <code>reverse</code> 部分</p>
<p><strong>全局上</strong><code>prev</code> 不动一直指向k个一组的起始部分, <code>curr</code>移动到k个一组末尾</p>
<p><strong>单次中</strong><code>prev</code>指向<code>curr</code> 指向的后一个节点, <code>curr</code> 向后移动</p>
<h3 id="随机链表的复制138">随机链表的复制(138)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public Node copyRandomList(Node head) {
if (head == null){
return null;
}
Map<Node, Node> map = new HashMap<>();
Node curr = head;
while (curr != null){
map.put(curr, new Node(curr.val));
curr = curr.next;
}
curr = head;
while (curr != null){
map.get(curr).next = map.get(curr.next);
map.get(curr).random = map.get(curr.random);
curr = curr.next;
}
return map.get(head);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>题目的要求是要<深拷贝>一组链表(要求各节点地址不同)</p>
<p>难点在于以<code>node.next</code>为方向<code>node.random</code> 可能会指向未初始化节点</p>
<p>所以我们要<strong>先一步初始化</strong>复制的链表, 再在之后的遍历中把<strong>新node</strong>进一步拷贝</p>
<p>如何最高效的进一步拷贝node呢, 有O(1)的复杂度就好了, 是什么呢, 好难猜啊🥰</p>
<h3 id="排序链表148">排序链表(148)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode fast = head.next, slow = head;
while (fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast.next != null){
fast = fast.next;
}
}
ListNode temp = slow.next;
slow.next = null;
ListNode lef = sortList(head);
ListNode rig = sortList(temp);
ListNode dummy = new ListNode(-1);
ListNode res = dummy;
while (lef != null && rig != null){
if (lef.val < rig.val){
dummy.next = lef;
lef = lef.next;
}else{
dummy.next = rig;
rig = rig.next;
}
dummy = dummy.next;
}
dummy.next = lef!=null ? lef : rig;
return res.next;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>根排序数组一样, 二分→排序→合并</p>
<ul>
<li>踩坑</li>
</ul>
<p>快慢指针在面对长度为2的链表, 没有快慢区分度 需要<code>ListNode fast = head.next</code> 让快指针先走一步</p>
<h3 id="合并k个升序链表023">合并K个升序链表(023)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mergeKLists(lists, 0, lists.length);
}
private ListNode mergeKLists(ListNode[] lists, int i, int j){
int m = j - i;
if (m == 0) return null;
if (m == 1) return lists;
ListNode lef = mergeKLists(lists, i, i + m/2);
ListNode rig = mergeKLists(lists, i + m/2, j);
return mergeTwoList(lef, rig);
}
private ListNode mergeTwoList() //实现同合并两个有序链表
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>同样, 先对k个链表进行K分→二分→排序→合并→K合</p>
<h3 id="lru缓存146">LRU缓存(146)</h3>
<p>先看代码</p>
<pre><code class="language-java"> 代码有点长 ,就不看了就看个总体吧
private static class Node {
int key, val;
Node prev, next;
Node (int k, int v){
key = k;
val = v;
}
}
private final int capacity;
private final Node dummy = new Node(0,0);
private final Map<Integer, Node> keyToNode = new HashMap<>();
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过 <strong>HashMap</strong>保证O(1)的增删改查 <strong>链表</strong>来排序节点的新旧</p>
<p>利用<code>prev, next</code> 形成以<code>dummy</code> 为介质的环形链表</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18924028
頁:
[1]