2023-07-31每日一题

一、题目编号

143. 重排链表

二、题目链接

点击跳转到题目位置

三、题目描述

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

	L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

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

示例 1：

示例 2：

提示：

• 链表的长度范围为 [1, 5 * 10⁴]
• 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 {
    ListNode* middleNode(ListNode* head){
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        while(fast->next != nullptr){
            fast = fast->next;
            slow = slow->next;
            if(fast->next != nullptr){
                fast = fast->next;
            }
        }
    return slow;
    }

    void reverseListNode(ListNode* head1, ListNode* tail){
        ListNode* p = head1->next;
        tail = p;
        while(p != nullptr){
            ListNode* q = p;
            p = p->next;
            if(q == tail){
                tail->next = nullptr;
                continue;
            }
            head1->next = q;
            q->next = tail;
            tail = q;
        }
    }
public:
    void reorderList(ListNode* head) {
        ListNode* mid = middleNode(head);
        reverseListNode(mid, mid->next);
        ListNode* head1 = head;
        ListNode* head2 = mid->next;
      
        while(head1 != nullptr && head2 != nullptr){
            if(head1 == mid){
                head1->next = nullptr;
            }
            ListNode*p = head1;
            head1 = head1->next;
            if(head1 == mid){
                head1->next = nullptr;
            }
            p->next = head2;
            ListNode*q = head2;
            head2 = head2->next;
            q->next = head1;
        }
       
    }
};

五、解题思路

(1) 使用分治的思路来解决问题。