LCR028-LCRO29双向链表和循环链表

剑指offer（专项突破版）4.5 双向链表和循环链表

LCR028.扁平化多级双向链表

分析

可以用递归的思想：

1. 基本情况（递归出口）：对于空节点或者已经是叶子节点（即没有子链表）的节点，不需要进行扁平化处理，直接返回。
2. 递归处理子链表：对于当前节点，如果存在子链表，我们需要先递归地扁平化子链表。
3. 连接扁平化后的子链表：将扁平化后的子链表连接到当前节点后面。
4. 继续处理下一个节点：继续递归处理当前节点的下一个节点。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* getFlattenTail(Node* head){
        Node* cur = head;
        Node* tail = NULL;  // 最终要返回的结点，子链表的最后一个结点
        // 递归出口：cur==NULL
        while(cur){
            // 保存next结点，以便在处理完子链表后链接到这个结点
            Node* next = cur->next;
            // 判断是否有子链表
            if(cur->child){
                Node* child = cur->child;    // 保存子结点
                cur->next = child;  // 改变cur的next指针
                child->prev = cur;  // 双向链表
                cur->child = NULL;  // 去掉子链表
                // 下面让子链表的最后一个结点指向next结点
                // 找到子链表的最后一个结点，要先扁平化子链表
                Node* childTail = getFlattenTail(child);
                childTail->next = next;
                if(next){
                    next->prev = childTail;
                }
                tail = childTail; // 更新tail
            }
            else{
                tail = cur;
            }
            cur = next;
        }
        return tail;
    }
    Node* flatten(Node* head) {
        getFlattenTail(head);
        return head;
    }
};

这种解法每个节点都会遍历一次，如果链表总共有n个节点，那么时间复杂度是O（n）。函数flattenGetTail的递归调用次数取决于链表嵌套的层数，因此，如果链表的层数为k，那么该节点的空间复杂度是O（k）。

LCR029.循环有序链表的插入

分析

先试图在链表中找到相邻的两个节点，如果这两个节点的前一个节点的值比待插入的值小并且后一个节点的值比待插入的值大，那么就将新节点插入这两个节点之间。如果找不到符合条件的两个节点，即待插入的值大于链表中已有的最大值或小于已有的最小值，那么新的节点将被插入值最大的节点和值最小的节点之间。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* node = new Node(insertVal);
        // 处理边界情况
        if(!head){
            head = node;
            head->next = head;
            return head;
        }
        if(head->next == head){
            head->next = node;
            node->next = head;
            return head;
        }
        // 找到值比insertVal小但next值比它大的结点
        Node* cur = head;
        Node* next = cur->next;
        Node* biggest = head;
        while(!(cur->val <= insertVal && next->val >= insertVal) && next != head){
            cur = next;
            next = next->next;
            if(cur->val >= biggest->val){
                biggest = cur;
            }
        }
        if(cur->val <= insertVal && next->val >= insertVal){
            cur->next = node;
            node->next = next;
        }
        else{
            next = biggest->next;
            biggest->next = node;
            node->next = next;
        }
        return head;
    }
};

注意if(cur->val >= biggest->val)这一判断条件必须是>=，因为需要更新到最后一个biggest。否则对于head=[1,3,3],insertVal=4这一输入，会得到[1,3,4,3]的错误结果。

总结

本章详细讨论了链表这种基础数据结构。由于节点在内存中的地址不连续，访问某个节点必须从头节点开始逐个遍历节点，因此在链表中找到某个节点的时间复杂度是O（n）。

如果一个操作可能产生新的头节点，则可以尝试在链表的最前面添加一个哨兵节点来简化代码逻辑，降低代码出现问题的可能性。

双指针是解决与链表相关的面试题的一种常用技术。前后双指针思路让一个指针提前走若干步，然后将第2个指针指向头节点，两个指针以相同的速度一起走。快慢双指针让快的指针每次走两步而慢的指针每次只走一步。

大部分与链表相关的面试题都是考查单向链表的操作。单向链表的特点是只能从前往后遍历而不能从后往前遍历。如果不得不从后往前遍历链表，则可以把链表反转之后再遍历。

如果链表中的节点除了有指向下一个节点的指针，还有指向前一个节点的指针，那么该链表就是双向链表。由于双向链表的操作牵涉到的指针比较多，因此应聘者在解决面试题的时候要格外小心，确保每个指针都指向了正确的位置。

循环链表是一种特殊形态的链表，它的所有节点都在一个环中。在解决与循环链表相关的面试题时需要特别注意避免死循环，遍历链表时等所有节点都遍历完就要停止，不能一直在里面绕圈子出不来。