每日OJ题_链表③_力扣143. 重排链表（反转链表合并链表）

目录

力扣143. 重排链表

解析代码

力扣143. 重排链表

143. 重排链表

难度 中等

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 10^4]
• 1 <= node.val <= 1000

/**
 * 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:
    void reorderList(ListNode* head) {

    }
};

解析代码

在C语言讲的数据结构里讲过这三道OJ：

206. 反转链表

876. 链表的中间结点

21. 合并两个有序链表

这道题就是先找到中间结点，分为两部分链表，然后翻转后部分链表，最后合并两个链表：

/**
 * 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:
    void reorderList(ListNode* head) {
        if(head==nullptr || head->next==nullptr || head->next->next==nullptr)
            return; // 处理边界情况

        ListNode *fast = head, *slow = head;
        while(fast && fast->next) // 找到中间结点
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* slowNext = slow->next;
        slow->next = nullptr; // 两个链表断开
        slow = slowNext;
        ListNode *reverseList = nullptr;
        while(slow) // 中间结点后面的头插到翻转链表
        {
            slowNext = slow->next;
            slow->next = reverseList;
            reverseList = slow;
            slow = slowNext;
        }

        ListNode* tmp = head; // 合并两个链表
        ListNode *cur1 = head->next, *cur2 = reverseList;
        while(cur1 && cur2)
        {
            tmp->next = cur2;
            tmp = tmp->next;
            cur2 = cur2->next;

            tmp->next = cur1;
            cur1 = cur1->next;
            tmp = tmp->next;
        }
    }
};