2023-07-31每日一題

一、題目編號

143. 重排鏈表

二、題目鏈接

點(diǎn)擊跳轉(zhuǎn)到題目位置

三、題目描述

給定一個單鏈表 L 的頭節(jié)點(diǎn) head ，單鏈表 L 表示為：

	L0 → L1 → … → Ln - 1 → Ln

請將其重新排列后變?yōu)椋?/p>

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

不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實際的進(jìn)行節(jié)點(diǎn)交換。

示例 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) 使用分治的思路來解決問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-624220.html

到了這里，關(guān)于2023-07-31 LeetCode每日一題（重排鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！