文章目录

• • 1.剑指 Offer II 026. 重排链表
  • 2.剑指 Offer II 027. 回文链表
  • 3.剑指 Offer II 028. 展平多级双向链表
  • 4.剑指 Offer II 029. 排序的循环链表

剑指 Offer II 026. 重排链表
剑指 Offer II 027. 回文链表
剑指 Offer II 028. 展平多级双向链表
剑指 Offer II 028. 展平多级双向链表

1.剑指 Offer II 026. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题目大意：将链表的后半部分逆序后，和前半部分交叉合并。

解题思路：找到链表的中心点，然后将中心点的后半部分逆序，最后合并前半部分和后半部分。

代码：

var reorderList = function(head) {if(head === null) return head;const  mid = midNode(head);let l1 = head, l2 = mid.next;l2 = reverseList(l2);mid.next = null;mergeList(l1, l2);
};function midNode(root) {let slow = root, fast = root;while(fast.next && fast.next.next) {slow = slow.next;fast =  fast.next.next;}return slow;
}function reverseList(root) {let pre = null, cur = root;while(cur) {const next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}function mergeList(l1, l2) {let p, q;while(l1 && l2) {p = l1.next;l1.next = l2;l1 = p;q = l2.next;l2.next = l1;l2 = q;}
}

2.剑指 Offer II 027. 回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

题目大意：判断一个链表是否是回文的

解题思路：递归。用一个全局变量存储当前匹配的最前面一个结点。

代码：

let preNode;function checkList(head) {if(head) {if(!checkList(head.next)) {return false;}if(head.val !== preNode.val) return false;preNode = preNode.next;}return true;
}var isPalindrome = function(head) {preNode = head;return checkList(head);
};

3.剑指 Offer II 028. 展平多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

题目大意：将一个多级双向链表合并成一个单级双向链表。

解题思路：bfs。若当前节点有子节点，就先处理当前节点。处理当前节点的子节点时，要注意处理子节点的前后节点指向。需要保证双向链表的特性。

代码：

var flatten = function(head) {const dfs = (node) => {let cur = node;let last = null;while(cur) {let next = cur.next;if(cur.child) {const lastChild = dfs(cur.child);next = cur.next;cur.next = cur.child;cur.child.prev = cur;if(next !== null) {lastChild.next = next;next.prev = lastChild;}cur.child = null;last = lastChild;} else {last = cur;}cur = next;}return last;}dfs(head);return head;
};

4.剑指 Offer II 029. 排序的循环链表

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

题目大意：在一个循环列表中，插入一个数使该循环链表仍然保持升序。

解题思路：首先处理head节点为空的情况，直接返回待插入值。然后处理两种情况：（1）待插入值为链表最值，找到链表最大值，在其后插入待插入值。（2）待插入值不是链表最值，找到待插入的位置插入。

代码：

var insert = function(head, insertVal) {const node = new Node(insertVal, null);node.next = node;if(head === null) return node;let p = head;while(p.next !== head) {if(insertVal >= p.val && insertVal <= p.next.val) {break;}if(p.val > p.next.val) {if(insertVal > p.val || insertVal < p.next.val) {break;}}p = p.next;}node.next = p.next;p.next = node;return head;
};