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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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