剑指 Offer（专项突击版）第27|28题
前言
- 现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第27|28题。
剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ， 请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
难度：简单
示例 1：
输入: head = [1,2,3,3,2,1] 输出: true
示例 2：
输入: head = [1,2] 输出: false
提示：
- 链表 L 的长度范围为 [1, 105]
- 0 <= node.val <= 9
进阶： 能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
方法一：链表中点 + 链表逆序 + 链表对比
如果不考虑辅助空间的限制，直观的解法是创建一个新的链表，链表中节点的顺序和输入链表的节点顺序正好相反。如果新的链表和输入链表是相同的，那么输入链表就是一个回文链表。这种解法需要创建一个和输入链表长度相等的链表，因此需要O（n）的辅助空间。
仔细分析回文链表的特点以找出更好的解法。回文链表的一个特性是对称性，如果把链表分为前后两半，那么前半段链表反转之后与后半段链表是相同的。
在如图所示的包含6个节点的链表中，前半段链表的3个节点反转之后分别是3、2、1，后半段链表的3个节点也分别是3、2、1，因此它是一个回文链表。如果链表的节点总数是奇数，那么把链表分成前后两半时不用包括中间节点。例如，一个链表中的节点顺序是1、2、k、2、1，前面两个节点反转之后是2、1，后面两个节点也是2、1，不管中间节点的值是什么该链表都是回文链表。
解法和题26相似，尝试把链表分成前后两半，然后把其中一半反转。
具体步骤：
a.第一步:初始化快慢指针slow、fast 都指向head，fast 每次走2步，slow 每次走1步，当fast走到最后的时候，slow位于中间位置，slow在移动的时候不断反转，反转后为prev
b.第二步:判断链表长度的奇偶性，奇数的情况下slow 再向后移动一步
c.第三步: slow 和 prev为链表前后半部分的头节点，判断 slow 和 prev开始到结尾的值，都相同返回true，否则返回false
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
let fast = head;
let slow = head;
let prev = null;
// 1.fast 走 2 步，slow 走 1 步，fast 走到最后的时候，slow 位于中间，反转 slow 前的链表
while (fast !== null && fast.next !== null) {
fast = fast.next.next;
// 反转链表
let next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// 2.fast !== null，说明链表为奇数，去掉中间的公共节点
if (fast !== null) slow = slow.next;
// 3.prev 为反转的链表头结点，slow 为链表的后半部分，判断 prev、slow 开始到结尾的节点值
while (prev !== null && slow !== null) {
if (prev.val !== slow.val) return false;
prev = prev.next;
slow = slow.next;
}
return true;
};
复杂度分析
- 时间复杂度：O(n)，其中 n 指的是链表的大小。
- 空间复杂度：O(1)。只修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。
剑指 Offer II 028. 展平多级双向链表
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。
难度：中等
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] 输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：
输入的多级列表如下图所示：
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3] 输出：[1,3,2] 解释： 输入的多级列表如下图所示： 1---2---NULL | 3---NULL
示例 3：
输入：head = [] 输出：[]
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null] [null,null,7,8,9,10,null] [null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示：
- 节点数目不超过 1000
- 1 <= Node.val <= 10^5
方法一：递归
由于子链表中的节点也可能有子链表，因此这里的链表是一个递归的结构。在展平子链表时，如果它也有自己的子链表，那么它嵌套的子链表也要一起展平。嵌套子链表和外层子链表的结构类似，可以用同样的方法展平，因此可以用递归函数来展平链表。
/**
* // Definition for a Node.
* function Node(val,prev,next,child) {
* this.val = val;
* this.prev = prev;
* this.next = next;
* this.child = child;
* };
*/
/**
* @param {Node} head
* @return {Node}
*/
var flatten = function(head) {
const dfs = (node) => {
let cur = node;
// 记录链表的最后一个节点
let last = null;
while (cur) {
let next = cur.next;
// 如果有子节点，那么首先处理子节点
if (cur.child) {
const childLast = dfs(cur.child);
next = cur.next;
// 将 node 与 child 相连
cur.next = cur.child;
cur.child.prev = cur;
// 如果 next 不为空，就将 last 与 next 相连
if (next != null) {
childLast.next = next;
next.prev = childLast;
}
// 将 child 置为空
cur.child = null;
last = childLast;
} else {
last = cur;
}
cur = next;
}
return last;
}
dfs(head);
return head;
};
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表中的节点个数。
- 空间复杂度：O(n)。上述代码中使用的空间为深度优先搜索中的栈空间，如果给定的链表的「深度」为 d，那么空间复杂度为 O(d)。在最换情况下，链表中的每个节点的 next 都为空，且除了最后一个节点外，每个节点的 child 都不为空，整个链表的深度为 n，因此时间复杂度为 O(n)。
so
传送门
转载自:https://juejin.cn/post/7188112317819650105