hot100之链表下
K个一组翻转链表(025)先看代码
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;
}
}
[*]分析
重点在 reverse 部分
全局上prev 不动一直指向k个一组的起始部分, curr移动到k个一组末尾
单次中prev指向curr 指向的后一个节点, curr 向后移动
随机链表的复制(138)
先看代码
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);
}
}
[*]分析
题目的要求是要一组链表(要求各节点地址不同)
难点在于以node.next为方向node.random 可能会指向未初始化节点
所以我们要先一步初始化复制的链表, 再在之后的遍历中把新node进一步拷贝
如何最高效的进一步拷贝node呢, 有O(1)的复杂度就好了, 是什么呢, 好难猜啊
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]