算法基础算法

问题拆解的威力，重排链表问题

字数统计: 957字   |   阅读时长: 3分
, , ,

摘要: 一个比较综合的链表题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本题的其中一种解法刚好是将链表上的三个常见问题(快慢指针，翻转链表，链表归并)串起来了。要点如下：

链表的更多问题参考 链表问题汇总。

本题是一个体现问题拆解的威力的极好例子：正确将问题拆解为若干步后，会发现其中的每一步都是已经解决过的问题。

$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题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 链表中点，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题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 翻转链表，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;
    }
};

step3: 合并有序链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
    }
};
Share