面试中常见的链表题目汇总

发表于 更新于 分类于 ，

重点解决 LeetCode 中 List 为 Top Interview Questions 且 Tag 为 Linked List 的题目。

0 如何写测试代码

以下是以 LeetCode 2 为例的，在 LeetCode Playground 完成的 C++ 实现及测试代码：

https://leetcode.com/playground/WmFSQPkU

其中，测试代码主要包含以下几个部分：

  • 定义单向链表节点：

    struct MyListNode {
        int val;
        MyListNode* next;
        MyListNode() : val(0), next(nullptr) {}
        MyListNode(int val) : val(val), next(nullptr) {}
        MyListNode(int val, MyListNode* next) : val(val), next  (next) {}
    };

  • 打印链表：

    void print_list(MyListNode* node) {
        std::ostringstream oss;
        while (node) {
            oss << node->val << "->";
            node = node->next;
        }
        oss << "NULL" << std::endl;
        std::cout << oss.str();
    }

  • 判断两个链表是否相等：

    bool is_equal_list(MyListNode* l1, MyListNode* l2) {
        if (!l1 && !l2) return true;
        if (!l1 || !l2 || l1->val != l2->val) return false;
        return is_equal_list(l1->next, l2->next);
    }

  • 将数组转换为链表：

    MyListNode* vec2list(const std::vector<int>& vec, int beg, int end) {
        int n = vec.size();
        if (end >= n || beg > end) return nullptr;
        MyListNode* node = new MyListNode(
            vec[beg], vec2list(vec, beg+1, end)
        );
        return node;
    }

    这样，我们就可以通过给定数组来测试链表了：

    std::vector<vector<int>> args_1 = {
        {},
        {},
        {1, 2, 3, 4},
        {8, 9, 9, 8},
    };
    std::vector<vector<int>> args_2 = {
        {},
        {1},
        {1, 2, 3, 4},
        {1, 2, 3, 4},
    };
    std::vector<vector<int>> rets = {
        {},
        {1},
        {2, 4, 6, 8},
        {9, 1, 3, 3, 1},
    };

  • 在主函数中测试：

    int main() {
        int n = rets.size();
        for (int i = 0; i < n; ++i) {
            MyListNode* arg_1 = vec2list(args_1[i], 0, args_1[i].size()-1);
            // print_list(arg_1);
            MyListNode* arg_2 = vec2list(args_2[i], 0, args_2[i].size()-1);
            // print_list(arg_2);
            MyListNode* ret = vec2list(rets[i], 0, rets[i].size()-1);
            // print_list(ret);
            assert(
                is_equal_list(add_two_numbers(arg_1, arg_2), ret)
            );
        }
    }

1 反转链表

LeetCode 206. Reverse Linked List

题意

给定一个链表，将其反转。

思路

以相邻三个元素 pre、cur 和 nxt 的处理过程为一个周期，在此周期内：

  1. 首先将 cur->next 记录到 nxt 中

  2. 然后将 cur->next 置为 pre，完成 cur 位置上的反转

  3. 最后将 pre 移动至 cur 的位置，将 cur 移动至 nxt 的位置

可以参考这个动图：How to Reverse Linked List

C++ 实现

/**
 * 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* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* pre = nullptr, *cur = head, *nxt = nullptr;
        while (cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

2 排序链表

LeetCode 148. Sort List

题意

给定一个链表，将其升序排序。

思路

使用归并排序或快速排序，基本思想与数组的排序算法保持一致，只是由于链表的特殊结构，在实现上要做特殊处理。

C++ 实现

归并排序：

/**
 * 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* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        return merge(sortList(head), sortList(fast));
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* root = new ListNode(), *cur = root;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) {
            cur->next = l1;
        } else {
            cur->next = l2;
        }
        return root->next;
    }
};

快速排序：

/**
 * 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* sortList(ListNode* head) {
        if (!head) return nullptr;
        quick_sort(head, nullptr);
        return head;
    }
    void quick_sort(ListNode* left, ListNode* right) {
        if (left == right || left->next == right) {
            return;
        }
        ListNode* mid = partition(left, right);
        quick_sort(left, mid);
        quick_sort(mid->next, right);
    }
    ListNode* partition(ListNode* left, ListNode* right) {
        int pivot = left->val;
        ListNode* pre = left, *cur = left->next;
        while (cur != right) {
            if (cur->val < pivot) {
                pre = pre->next;
                swap_pointer(pre, cur);
            }
            cur = cur->next;
        }
        swap_pointer(left, pre);
        return pre;
    }
    void swap_pointer(ListNode* l1, ListNode* l2) {
        int v = l1->val;
        l1->val = l2->val;
        l2->val = v;
    }
};