//Java class Solution { public String decodeString(String s) { StringBuilder res = new StringBuilder(); int multi = 0; LinkedList<Integer> stack_multi = new LinkedList<>(); LinkedList<String> stack_res = new LinkedList<>(); for(Character c : s.toCharArray()) { if(c == '[') { stack_multi.addLast(multi); stack_res.addLast(res.toString()); multi = 0; res = new StringBuilder(); } else if(c == ']') { StringBuilder tmp = new StringBuilder(); int cur_multi = stack_multi.removeLast(); for(int i = 0; i < cur_multi; i++) tmp.append(res); res = new StringBuilder(stack_res.removeLast() + tmp); } else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + ""); else res.append(c); } return res.toString(); } }
复杂度分析
时间复杂度 O(N)，一次遍历 s；
空间复杂度 O(N)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。
（2）递归
思路及算法
总体思路与辅助栈法一致，不同点在于将 [ 和 ] 分别作为递归的开启与终止条件：
当 s[i] == ']' 时，返回当前括号内记录的 res 字符串与 ] 的索引 i （更新上层递归指针位置）；
当 s[i] == '[' 时，开启新一层递归，记录此 [...] 内字符串 tmp 和递归后的最新索引 i，并执行 res + multi * tmp 拼接字符串。
//Java class MinStack { Deque<Integer> xStack; Deque<Integer> minStack;
public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于x 的节点都出现在 大于或等于x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
1 2
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
1 2
输入：head = [2,1], x = 2 输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
2.解法
模拟
思路及算法
直观来说我们只需维护两个链表 small 和 large 即可，small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。
为了实现上述思路，我们设 smallHead 和 largeHead 分别为两个链表的哑节点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。同时设 small 和 large 节点指向当前链表的末尾节点。开始时 smallHead=small,largeHead=large。随后，从前往后遍历链表，判断当前链表的节点值是否小于 x，如果小于就将 small 的 next 指针指向该节点，否则将 large 的 next 指针指向该节点。
遍历结束后，我们将 large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。同时将 small 的 next 指针指向 largeHead 的 next 指针指向的节点，即真正意义上的 large链表的头节点。最后返回 smallHead的 next 指针即为我们要求的答案。
//Java class Solution { public ListNode rotateRight(ListNode head, int k) { if (k == 0 || head == null || head.next == null) { return head; } int n = 1; ListNode iter = head; while (iter.next != null) { iter = iter.next; n++; } int add = n - k % n; if (add == n) { return head; } iter.next = head; while (add-- > 0) { iter = iter.next; } ListNode ret = iter.next; iter.next = null; return ret; } }
while (cur != nullptr) { ListNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } }
public: ListNode *reverseBetween(ListNode *head, int left, int right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 ListNode *dummyNode = new ListNode(-1); dummyNode->next = head;
ListNode *pre = dummyNode; // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (int i = 0; i < left - 1; i++) { pre = pre->next; }
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 ListNode *rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode->next; }
//Java class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论 ListNode dummyNode = new ListNode(-1); dummyNode.next = head;
ListNode pre = dummyNode; // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (int i = 0; i < left - 1; i++) { pre = pre.next; }
// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; }
//Java class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 设置 dummyNode 是这一类问题的一般做法 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; for (int i = 0; i < left - 1; i++) { pre = pre.next; } ListNode cur = pre.next; ListNode next; for (int i = 0; i < right - left; i++) { next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return dummyNode.next; } }
//Java class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode ans = null; for (int i = 0; i < lists.length; ++i) { ans = mergeTwoLists(ans, lists[i]); } return ans; }
public ListNode mergeTwoLists(ListNode a, ListNode b) { if (a == null || b == null) { return a != null ? a : b; } ListNode head = new ListNode(0); ListNode tail = head, aPtr = a, bPtr = b; while (aPtr != null && bPtr != null) { if (aPtr.val < bPtr.val) { tail.next = aPtr; aPtr = aPtr.next; } else { tail.next = bPtr; bPtr = bPtr.next; } tail = tail.next; } tail.next = (aPtr != null ? aPtr : bPtr); return head.next; } }
复杂度分析
时间复杂度：假设每个链表的最长长度是 n。在第一次合并后，ans 的长度为 n；第二次合并后，ans 的长度为 2×n，第 i 次合并后，ans 的长度为 i×n。第 i 次合并的时间代价是 O(n+(i−1)×n)=O(i×n)，那么总的时间代价为 O(k^2^n)，故渐进时间复杂度为 O(k^2^ n)。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
1 2
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
1 2
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
2.解法
思路及算法
链表分区为已翻转部分+待翻转部分+未翻转部分；每次翻转前，要确定翻转链表的范围，这个必须通过 k 次循环来确定；需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来；初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾；经过k次循环，end 到达末尾，记录待翻转链表的后继 next = end.next；翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环；特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可。
//Java public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next = head;
ListNode pre = dummy; ListNode end = dummy;
while (end.next != null) { for (int i = 0; i < k && end != null; i++) end = end.next; if (end == null) break; ListNode start = pre.next; ListNode next = end.next; end.next = null; pre.next = reverse(start); start.next = next; pre = start;
end = pre; } return dummy.next; }
private ListNode reverse(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; }
//Java class Solution { Map<Node, Node> cachedNode = new HashMap<Node, Node>();
public Node copyRandomList(Node head) { if (head == null) { return null; } if (!cachedNode.containsKey(head)) { Node headNew = new Node(head.val); cachedNode.put(head, headNew); headNew.next = copyRandomList(head.next); headNew.random = copyRandomList(head.random); } return cachedNode.get(head); } }
复杂度分析
时间复杂度：O(n)，其中 n 是链表的长度。对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。
空间复杂度：O(n)，其中 n 是链表的长度。为哈希表的空间开销。
（2）迭代+节点拆分
思路及算法
我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′。对于任意一个原节点 S，其拷贝节点 S’ 即为其后继节点。这样，我们可以直接找到每一个拷贝节点 S′ 的随机指针应当指向的节点，即为其原节点 S 的随机指针指向的节点 T 的后继节点 T′ 。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。
