面试题｜【面试好题】1. 重排链表
FennelDumplings
3128
2021.07.24
发布于 未知归属地
链表C++面试题求职面试

最近公司的面试需求比较多，由于是小厂，不像大厂的标准化的考查流程和题库，虽然有一些可以自由发挥的余地，但是面试题就得准备准备了。我主要招算法工程师的校招和3年以下的社招。算法这块基本就是考一道 leetcode medium 级别的题。

我之前有积累一些适合面试的题，之后就一直在用，不过很少(5道以内)，最近开始回炉 leetcode 是想找一找新的适合面试的题。

最近打算试着写一写 leetcode 上我认为比较适合面试的题，每篇文章拆解一道题，看看连载到多少期就连载不动了。

以下几个要点中 (1)(2)(5)必须满足，(3)(4)至少满足一个：
(1) 考查基础的数据结构和主流算法，避开邪门算法和脑筋急转弯
(2) 暴力方法很容易想到
(3) 最好有两种以上的优化方式
(4) 最好有两三道递进的题可以放到一起
(5) 最终代码不长

这是面试好题连载的第1期，今天我们看一个我之前经常用的题：leetcode第143题，重排链表。本题可以拆解成 3 个比较基本的题，而拆解出来的子问题各自都是很经典的问题和方法。将子问题依次解决，在前后组合到一起，就成了本题的答案。在一个题中考察了多个题的算法要点，同时还考察了拆解问题的能力。

本题的完整解法刚好是将链表上的三个常见问题(快慢指针，翻转链表，链表合并)串起来了。

$1 题目

题目链接

143. 重排链表

题目描述

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

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

样例

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

$2 题解

算法

整个流程分为几个步骤，

第一步后得到中点指针 middlenode，链表结构没有改变。第二步反转之后，原来中点的前一个节点的 next 仍指向原来中点，原来中点的 next 已经是 nullptr。middlenode 变成了原链表的最后一个节点，如图A。

归并的两个链表是 head 和 middlenode，轮流从两个表取，不论节点个数奇偶，两个链表最终一定会相交，相交即为归并结束的条件。

代码(C++)

前两步，也就是找链表的中间节点，以及反转链表，都可以直接用 leetcode 原题的代码，下面直接给出这两个子需求的代码

step1: 找链表中点(leetcode第786题)

// 链表中点，lc786
class Solution_786 {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == nullptr || head -> next == nullptr) return head;
        ListNode *slow = head, *fast = head;
        while(fast != nullptr && fast -> next != nullptr)
        {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        return slow;
    }
};

step2: 反转链表(leetcode第206题)

// 翻转链表，lc206
class Solution_206 {
public:
    ListNode* reverseList(ListNode* head) {
        // 空链表
        if(head == nullptr) return head;
        // 只有一个元素的链表
        if(head -> next == nullptr) return head;

        // 至少两个元素，iter初始为第二个
        ListNode *iter = head -> next;
        head -> next = nullptr;
        ListNode *result = reverseList(iter);
        iter -> next = head;
        return result;
    }
};

第三步由于需要在合并两个有序链表的代码上修改一下。所以不能直接用原题的代码，而是要按照前的分析过程重新写。下面是本题的代码

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        Solution_786 solution786;
        Solution_206 solution206;
        ListNode *middlenode = solution786.middleNode(head);
        middlenode = solution206.reverseList(middlenode);
        ListNode *iter1 = head, *iter2 = middlenode;
        ListNode dummy_node(0);
        ListNode *dummy = &dummy_node;
        ListNode *iter = dummy;
        int flag = 1;
        while(iter1 != iter2)
        {
            if(flag & 1)
            {
                iter -> next = iter1;
                iter1 = iter1 -> next;
                iter = iter -> next;
                flag ^= 1;
            }
            else
            {
                iter -> next = iter2;
                iter2 = iter2 -> next;
                iter = iter -> next;
                flag ^= 1;
            }
        }
        iter -> next = iter1;
        head = dummy -> next;
    }
};
评论 (2)