链表：其他

0138. 复制带随机指针的链表 (opens new window)

题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

解析

首先通过一次遍历存储原始节点与拷贝节点的映射关系，之后再通过一次遍历存储点与点之间的关系。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> h;
        for (Node* cur = head; cur; cur = cur->next) {
            h[cur] = new Node(cur->val);
        }
        for (Node* cur = head; cur; cur = cur->next) {
            if (cur->next) h[cur]->next = h[cur->next];
            if (cur->random) h[cur]->random = h[cur->random];
        }
        return h[head];
    }
};

0143. 重排链表 (opens new window)

题目

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解析

将链表从中间分成两部分，将后部分链表反转，然后同时遍历两链表进行拼接。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *mid = getMidNode(head);
        ListNode *next = reverse(mid->next);
        mid->next = nullptr;
        merge(head, next);
    }

    void merge(ListNode* l1, ListNode* l2) {
        while (l1 && l2) {
            ListNode *n1 = l1->next, *n2 = l2->next;
            l1->next = l2, l2->next = n1;
            l1 = n1, l2 = n2;
        }
    }

    ListNode* getMidNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverse(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while (cur) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

0234. 回文链表 (opens new window)

题目

请判断一个链表是否为回文链表。

解析

找到链表中点，将后半部分链表反转，然后逐个比较前后链表对应结点的值，这样可以在 $$

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode* middle = _getMiddle(head);
        ListNode* next = _reverseList(middle->next);
        while (next) {
            if (head->val != next->val) {
                return false;
            }
            head = head->next;
            next = next->next;
        }
        return true;
    }

    ListNode* _getMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* _reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* pre = NULL;
        while (head) {
            ListNode* tmp = head->next;
            head->next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
};

0430. 扁平化多级双向链表 (opens new window)

题目

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

解析

递归写法，当遇到含有子节点的节点时，进行以下步骤：

1. 保存 next 节点；
2. 递归获取当前子节点的扁平化结果，并与当前节点相连；
3. 将 next 节点拼接到子节点的扁平化结果之后。

代码

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

class Solution {
public:
    Node* flatten(Node* head) {
        Node* node = head;
        while (node) {
            if (node->child) {
                Node* next = node->next;
                
                node->next = flatten(node->child);
                node->next->prev = node;
                node->child = nullptr;
                while (node->next) {
                    node = node->next;
                }

                if (next) {
                    node->next = next;
                    node->next->prev = node;
                }
            }
            node = node->next;
        }
        return head;
    }
};

0445. 两数相加 II (opens new window)

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

解析

将两链表分别入栈，接着成对弹出栈顶元素相加，将其拼接成结果链表。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        
        ListNode* cur = new ListNode(0);
        
        int sum = 0;
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }
            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }
            cur->val = sum % 10;
            ListNode* head = new ListNode(sum / 10);
            head->next = cur;
            cur = head;
            sum /= 10;
        }
        return cur->val == 0 ? cur->next : cur;
    }
};