LeetCode 链表

LeetCode 链表

题目

1. 常规题

2 两数相加

给两个链表分别代表两个正数的逆序表示,计算两个链表之和。

依次按位进行相加。

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int acc = 0, val = 0;
        auto head = l1, tail = l1;
        while (l1 && l2) {
            val = l1->val + l2->val + acc;
            acc = val / 10;
            l1->val = val % 10;
            if (!l1->next)
                l1->next = l2->next, l2->next = nullptr;
            tail = l1;
            l1 = l1->next, l2 = l2->next;
        }
        while (l1) {
            val = l1->val + acc;
            acc = val / 10;
            l1->val = val % 10;
            tail = l1;
            l1 = l1->next;
        }
        if (acc)
            tail->next = new ListNode(1);
        return head;
    }
};

21 合并两个有序链表

合并两个有序链表。

逐个比较大小并添加到当前节点后面,并移动对应的链表节点。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0), *node = head;
        while (l1 && l2) {
            if (l1->val < l2->val)
                head->next = l1, l1 = l1->next;
            else
                head->next = l2, l2 = l2->next;
            head = head->next;
        }
        while (l1)
            head->next = l1, l1 = l1->next, head = head->next;
        while (l2)
            head->next = l2, l2 = l2->next, head = head->next;
        return node->next;
    }
};

83 删除排序链表中的重复元素

删除链表中所有重复的节点。

将每个节点与其后面的节点的值做对比,如果相同则删除后面的节点。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto ret = head;
        while (head) {
            while (head->next && head->next->val == head->val) {
                auto next = head->next;
                head->next = next->next;
                delete next;
            }
            head = head->next;
        }
        return ret;
    }
};

82 删除排序链表中的重复元素 II

删除链表中所有重复的节点,只保留原始链表中没有重复出现的数字。

为了删除所有重复的节点并只保留所有没有出现过的数字,需要提前两个节点检查接下来的两个节点的值是否相同,如果相同的话需要将这两个节点及其后的所有重复节点都删除。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *node = new ListNode(0), *ret = node, *next = nullptr, *temp = nullptr;
        node->next = head;
        while (node && node->next) {
            next = node->next->next;
            while (next && node->next->val == next->val) {
                temp = next;
                next = next->next;
                delete temp;
            }
            if (next != node->next->next) {
                temp = node->next;
                node->next = next;
                delete temp;
            } else
                node = node->next;
        }
        return ret->next;
    }
};

203 移除链表元素

删除链表中等于给定值的所有节点。

先判断头节点是否等于给定值,再判断其后面的节点是否等于给定值。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head && head->val == val) {
            auto prev = head;
            head = head->next;
            delete prev;
        }
        auto ret = head;
        while (head) {
            while (head->next && head->next->val == val) {
                auto next = head->next;
                head->next = next->next;
                delete next;
            }
            head = head->next;
        }
        return ret;
    }
};

817 链表组件

给一个链表和一个数组,找到链表中一段子链表的值都在数组中的子链表的个数。

先将数组转换成哈希表方便查询,再依次遍历整个链表,判断一段子链表结束时或遍历结束时子链表是否是符合条件。

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        unordered_set<int> exist(G.begin(), G.end());
        bool cont = false, curr = false;
        int res = 0;
        while (head) {
            curr = exist.count(head->val);
            res += cont && !curr;
            cont = curr;
            head = head->next;
        }
        return res + cont;
    }
};

24 两两交换链表中的节点

给一个链表,返回两两交换其中相邻的节点后的结果。

用三个指针把要交换的两个节点和他们的前驱节点保存下来,交换后再更新三个指针,按顺序交换即可。

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *root = new ListNode(0), *prev = root;
        root->next = head;
        auto first = head, second = head->next;
        while (first && second) {
            auto temp = second->next;
            prev->next = second;
            second->next = first;
            first->next = temp;
            prev = first;
            first = temp;
            second = temp ? temp->next : nullptr;
        }
        return root->next;
    }
};

430 扁平化多级双向链表

给一个带子节点的双向链表,将其扁平化并使所有结点出现在单级双链表中。

对于某一个节点,如果它有 child 节点,那么需要将其 child 节点作为其新的 next 节点,将其 child 链表上的最后一个节点作为其原本 next 节点的 prev 节点,递归调用整个过程即可。

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

2. 链表反转

206 反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *prev = nullptr, *curr = head, *next = head->next;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

92 反转链表 II

将链表中从 m 到 n 位置的节点反转。

先找到位置在 m - 1 的节点,将其后的节点截断,再找到位置在 n 的节点,将其后的节点截断,将中间的一段链表反转后再链接到愿链表上。

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *root = new ListNode(0), *r = root, *prev, *last;
        root->next = head;
        int cnt = 1;
        while (cnt < m && r)
            r = r->next, ++cnt;
        prev = r;
        while (cnt <= n && r && r->next)
            r = r->next, ++cnt;
        last = r->next;
        r->next = nullptr;
        prev->next = Reverse(prev->next);
        while (prev && prev->next)
            prev = prev->next;
        prev->next = last;
        return root->next;
    }

    ListNode *Reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

369 给单链表加一

用一个单链表表示一个整数,计算将其加一的结果。

先将链表反转方便进位,然后进行加一和进位的操作,最后再反转一次链表。

class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        if (!head)
            return nullptr;
        head = Reverse(head);
        auto root = head;
        while (head) {
            if (head->val == 9) {
                head->val = 0;
                if (!head->next) {
                    head->next = new ListNode(1);
                    break;
                }
                head = head->next;
            }
            else {
                ++head->val;
                break;
            }
        }
        return Reverse(root);
    }
    
    ListNode *Reverse(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *prev = nullptr, *curr = head, *next = head->next;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

445 两数相加 II

给两个链表分别代表两个正数,计算两个链表之和。

先将两个链表反转,再依次按位进行相加,最后再将得到的结果反转并返回。

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (!l1 || !l2)
            return !l1 ? l2 : l1;
        l1 = Reverse(l1);
        l2 = Reverse(l2);
        int carry = 0, sum = 0;
        ListNode *head = l1, *prev = l1;
        while (l1 && l2) {
            prev = l1;
            sum = l1->val + l2->val + carry;
            carry = sum / 10;
            l1->val = sum - carry * 10;
            if (l2->next && !l1->next)
                l1->next = l2->next, l2->next = nullptr;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1) {
            prev = l1;
            sum = l1->val + carry;
            carry = sum / 10;
            l1->val = sum - carry * 10;
            l1 = l1->next;
        }
        if (carry && prev)
            prev->next = new ListNode(1);
        return Reverse(head);
    }

    ListNode *Reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

3. 双链表

328 奇偶链表

把一个链表中的奇数位节点和偶数位节点分别排在一起。

用两个头节点分别表示奇数位和偶数位节点的起始位置,遍历整个链表,将奇数位节点链接在奇数位起始节点后,将偶数位节点链接在偶数位起始节点后,最后将偶数位起始节点链接在奇数位最后节点后即可。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next)
            return head;
        auto odd = head, even = head->next, node = even->next, even_head = even;
        bool flag = true;
        while (node) {
            if (flag) {
                odd->next = node;
                odd = odd->next;
                flag = false;
            } else {
                even->next = node;
                even = even->next;
                flag = true;
            }
            node = node->next;
        }
        odd->next = even_head;
        even->next = nullptr;
        return head;
    }
};

86 分隔链表

给一个链表和一个值 x,重新排列链表使得所有小于 x 的节点都在大于等于 x 的节点之前。

用两个头节点 sth 和 geq 分别表示小于 x 和大于等于 x 的节点的起始位置,遍历整个链表,分别将各个节点链接到两个头节点之后,最后将 geq 链接到 sth 之后,再将 geq 的末端设为空指针。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        auto sth = new ListNode(0), sth_head = sth, geq = new ListNode(0), geq_head = geq;
        while (head) {
            if (head->val < x) {
                sth->next = head;
                sth = sth->next;
            } else {
                geq->next = head;
                geq = geq->next;
            }
            head = head->next;
        }
        sth->next = geq_head->next;
        geq->next = nullptr;
        return sth_head->next;
    }
};

725 分隔链表

给一个链表, 将其分隔为 k 个连续的部分。

先计算出链表的长度和 k 个连续部分中每个部分的长度,依次将每个部分的头节点放入数组中。

class Solution {
public:
    vector<ListNode *> splitListToParts(ListNode *root, int k) {
        vector<ListNode *> res(k, nullptr);
        int len = 0;
        ListNode *head = root, *temp = nullptr;
        while (root)
            root = root->next, ++len;
        int n = len / k, m = len % k, i = 0;
        while (head) {
            res[i] = head;
            for (int j = 0; j < n + (m > 0) - 1; ++j)
                head = head->next;
            temp = head;
            head = head->next;
            temp->next = nullptr;
            ++i;
            --m;
        }
        return res;
    }
};

4. 双指针

876 链表的中间结点

找链表的中间节点。

用两个指针 slow 和 fast,fast 每次移动两步,slow 每次移动一步,当 fast 走到末尾的时候 slow 恰好到指针的中间。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto slow = head, fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

160 相交链表

找到两个链表相交的起始节点。

假设链表 A 未相交的长度为 l1,链表 B 未相交的长度为 l2,相交部分的长度为 lc,为了让两个指针走相同的长度,只需要让两个指针在走到尾部的时候重新回到另一个链表的头部再继续走,最后当两个指针走过的长度都是 l1 + l2 + l3 时即相交。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto a = headA, b = headB;
        if (!a || !b)
            return nullptr;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};

141 环形链表

判断一个链表中是否有环。

用两个指针 slow 和 fast,fast 每次移动两步,slow 每次移动一步,如果链表中有环那么这两个指针一定会最终相遇,否则 fast 将先到达末尾,当 fast == nullptr 或 fast->next == nullptr 即代表链表没有换并且 fast 已经到达末尾。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto slow = head, fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                return true;
        }
        return false;
    }
};

142 环形链表 II

给一个链表,找到链表中入环的第一个节点。

跟上一题相同,用两个指针 slow 和 fast,fast 每次移动两步,slow 每次移动一步,如果链表中有环那么这两个指针一定会最终相遇,此时 fast 指针移动的距离是 l1 + l2 + c,其中 l1 是链表中环外部分的长度,l2 是环内两个指针走过的共同部分的长度,c 是环的长度,而 slow 指针移动的距离则是 l1 + l2,因为 fast 指针的移动速度是 slow 的两倍,所以有 l1 + l2 + c = 2 * (l1 + l2),因此 c = l1 + l2,又因为 slow 指针已经在环中走过了长度为 l2 的部分,只剩下长度为 l1 的部分,只需要用一个新的指针从链表的头部开始每次移动一步,同时让 slow 指针每次移动一步,最终他们都会移动 l1 的距离并在入环处相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next)
            return nullptr;
        auto slow = head->next, fast = head->next->next;
        while (fast && fast->next && fast != slow) {
            fast = fast->next->next;
            slow = slow->next;
        }
        if (!fast || !fast->next)
            return nullptr;
        auto lin = head;
        while (lin != slow)
            lin = lin->next, slow = slow->next;
        return lin;
    }
};

61 旋转链表

给一个链表,将其每个节点向右移动 k 个位置。

在链表中不易直接取到前 k 个位置,所以用两个指针,第一个先往前走 k 步,然后两个指针一起往前走直到第一个指针没有后继指针,就可以将头节点链接到第一个指针后,将第二个指针后置为空。注意 k 可能非常大,要先计算一次链表的长度 len 然后用 k % len 进行计算。

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if (!head)
            return nullptr;
        ListNode *first = head, *second = head, *traverse = head;
        int len = 0;
        while (traverse) {
            traverse = traverse->next;
            ++len;
        }
        k %= len;
        for (int i = 0; i < k; i++)
            first = first->next;
        while (first && first->next)
            first = first->next, second = second->next;
        first->next = head;
        auto ret = second->next;
        second->next = nullptr;
        return ret;
    }
};

5. 综合

234 回文链表

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

先找到链表的中间节点,然后将右边的链表翻转,将左边的链表从中间截断,再一次对比两边的每一个节点是否相等。

class Solution {
public:
    bool isPalindrome(ListNode *head) {
        if (!head || !head->next)
            return true;
        auto prev = head, slow = head, fast = head;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        auto node = Reverse(fast ? slow->next : slow);
        prev->next = nullptr;
        while (head && node && head->val == node->val)
            head = head->next, node = node->next;
        return !head && !node;
    }
    
    ListNode *Reverse(ListNode *head) {
        if (!head)
            return head;
        ListNode *prev = nullptr, *curr = head, *next = head->next;
        while(curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

109 有序链表转换二叉搜索树

给一个有序链表,将其转换为一个平衡二叉搜索树。

先找到链表的中间节点,将其作为树的根节点,将中间节点的左边部分链表作为其左子树,右边部分链表作为其右子树。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if (!head)
            return nullptr;
        ListNode *prev = nullptr, *slow = head, *fast = head;
        while (fast && fast->next)
            prev = slow, slow = slow->next, fast = fast->next->next;
        if (prev)
            prev->next = nullptr;
        auto root = new TreeNode(slow->val);
        root->left = sortedListToBST(prev ? head : nullptr);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

426 将二叉搜索树转化为排序的双向链表

将一个二叉搜索树转换为一个双向循环链表。

对于一个根节点,其被转换为双向链表之后的前驱节点应该是其左子树中值最大的节点,也就是其左子节点的最右子节点,因此只需要先找到这个节点,然后将根节点与其首尾相连即可,在此之前应该先对根节点的左子树左对应的操作,右子树亦然。除此之外还要把最小的和最大的两个节点保存下来,将这两个节点首尾相连,形成循环链表。

class Solution {
    Node *first, *last;
public:
    Node *treeToDoublyList(Node *root) {
        first = last = nullptr;
        TreeToList(root);
        if (first)
            first->left = last;
        if (last)
            last->right = first;
        return first;
    }

    void TreeToList(Node *root) {
        if (!root)
            return;
        if (!first || first->val > root->val)
            first = root;
        if (!last || last->val < root->val)
            last = root;
        auto left = root->left, right = root->right;
        TreeToList(left);
        TreeToList(right);
        while (left && left->right)
            left = left->right;
        if (left)
            left->right = root;
        root->left = left;
        while (right && right->left)
            right = right->left;
        if (right)
            right->left = root;
        root->right = right;
    }
};

143 重排链表

将一个链表从 L0→L1→…→Ln-1→Ln 重新排列为 L0→Ln→L1→Ln-1→L2→Ln-2→…。

先将链表从中间分为两部分,将后半部分反转,再将对应位置的节点依次链接上。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head)
            return;
        auto prev = head, slow = head, fast = head, first = head, second = head;
        while (fast && fast->next)
            prev = slow, slow = slow->next, fast = fast->next->next;
        if (fast) {
            second = slow->next;
            slow->next = nullptr;
        } else {
            second = slow;
            prev->next = nullptr;
        }
        second = Reverse(second);
        while (second) {
            auto n1 = first->next, n2 = second->next;
            first->next = second;
            second->next = n1;
            first = n1;
            second = n2;
        }
    }
    
    ListNode *Reverse(ListNode *head) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};
comments powered by Disqus