hot100之链表下

K个一组翻转链表(025)

先看代码

1. class Solution {
2.     public ListNode reverseKGroup(ListNode head, int k) {
3.         ListNode dummy = new ListNode(-1, head);
4.         ListNode prev = dummy;
5.         while(prev.next != null){
6.             ListNode curr = reverse(prev, k);
7.             if (curr == null){
8.                 reverse(prev, k);
9.                 break;
10.             }
11.             prev = curr;
12.         }
14.         return dummy.next;
15.     }
17.     private ListNode reverse(ListNode prev, int k){
18.         ListNode curr = prev.next;
19.         int i = 1;
20.         for (;i < k && curr.next != null; i++){
21.             ListNode next = curr.next;
22.             curr.next = next.next;
23.             next.next = prev.next;
24.             prev.next = next;
25.         }
26.         return i < k ? null : curr;
27.     }
28. }

复制代码

• 分析
  

重点在 reverse 部分
全局上prev 不动一直指向k个一组的起始部分, curr移动到k个一组末尾
单次中prev指向curr 指向的后一个节点, curr 向后移动
随机链表的复制(138)

先看代码

1. class Solution {
2.     public Node copyRandomList(Node head) {
3.         if (head == null){
4.             return null;
5.         }
6.         Map<Node, Node> map = new HashMap<>();
7.         Node curr = head;
8.         while (curr != null){
9.             map.put(curr, new Node(curr.val));
10.             curr = curr.next;
11.         }
13.         curr = head;
14.         while (curr != null){
15.             map.get(curr).next = map.get(curr.next);
16.             map.get(curr).random = map.get(curr.random);
17.             curr = curr.next;
18.         }
20.         return map.get(head);
21.     }
22. }

复制代码

• 分析
  

题目的要求是要一组链表(要求各节点地址不同)
难点在于以node.next为方向node.random 可能会指向未初始化节点
所以我们要先一步初始化复制的链表, 再在之后的遍历中把新node进一步拷贝

如何最高效的进一步拷贝node呢, 有O(1)的复杂度就好了, 是什么呢, 好难猜啊
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！