Reorder List（C++重排链表）

- 日理万妓 2023-01-20 05:59 39阅读 0赞

（1）寻找中点，断点

（2）反转链表

（3）合并链表

/**
     * 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:
        ListNode* middleNode(ListNode* head) {
            ListNode *slow=head,*fast=head;
            while(fast!=nullptr && fast->next!=nullptr) {
                slow=slow->next;
                fast=fast->next->next;
            }
            return slow;
        }
        
        ListNode* reverseList(ListNode* head) {
            ListNode *pre=nullptr,*cur=head;
            while(cur) {
                ListNode *temp=cur->next;
                cur->next=pre;
                pre=cur;
                cur=temp;
            }
            return pre;
        }
        
        ListNode* merge(ListNode* head1,ListNode* head2) {
            ListNode *phead1=head1,*phead2=head2;
            while(phead1!=nullptr && phead2!=nullptr) {
                ListNode *p1=phead1->next;
                ListNode *p2=phead2->next;
                phead1->next=phead2;
                if(p1==nullptr) {
                    phead2->next=p2;
                } else phead2->next=p1;
                
                phead1=p1;
                phead2=p2;
            }
            return head1;
        }
        
        void reorderList(ListNode* head) {
            ListNode* l=middleNode(head);
            ListNode* mid=l->next;
            l->next=nullptr;
            mid=reverseList(mid);
            merge(head,mid);
            return;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，39人围观）

还没有评论，来说两句吧...

相关阅读

相关【PTA】重排链表

题目重述给定一个单链表 `L1 →L2 →⋯→Ln−1 →Ln` ，请编写程序将链表重新排列为 `Ln →L1 →Ln−1 →L2 →⋯`。例如：给定L为1→2→3→4

我就是我/ 2023年07月04日 06:10/ 0 赞/ 56 阅读

相关（Java）leetcode-143 Reorder List（重排链表）

题目描述给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部

小鱼儿/ 2023年02月23日 05:26/ 0 赞/ 56 阅读

相关 143. 重排链表

题目来源 [143. 重排链表][143.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

曾经终败给现在/ 2023年02月20日 15:55/ 0 赞/ 113 阅读

相关 Reorder List（C++重排链表）

（1）寻找中点，断点（2）反转链表（3）合并链表 / Definition for singly-linked list. struc

- 日理万妓/ 2023年01月20日 05:59/ 0 赞/ 40 阅读

相关 144-重排链表

题目如下：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部

阳光穿透心脏的1/2处/ 2023年01月09日 15:36/ 0 赞/ 204 阅读

相关 143. 重排链表

> 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， > 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… > > 你不能只是单纯的改变节点内部

落日映苍穹つ/ 2022年10月07日 07:48/ 0 赞/ 252 阅读

相关 [Leetcode][python]Reorder List/重排链表

题目大意将单向链表`L0→L1→…→Ln-1→L`n转化为`L0→Ln→L1→Ln-1→L2→Ln-2→…`的形式，也就是从头部取一个节点，从尾部取一个节点，直到将原链

淡淡的烟草味﹌/ 2022年06月03日 02:59/ 0 赞/ 269 阅读

相关链表15--重排链表

1、题目： -------------------- Given a singly linked list L: L0→L1→…→Ln\-1→Ln, reorder i

灰太狼/ 2022年05月25日 07:17/ 0 赞/ 264 阅读

相关 LeetCode 143.Reorder List (重排链表)

题目描述：给定一个单链表 L：L0→L1→…→Ln\-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln\-1→L2→Ln\-2→… 你不能只是单纯的改变节点

拼搏现实的明天。/ 2022年05月08日 13:26/ 0 赞/ 250 阅读

相关【Leetcode】143. Reorder List（链表）

Given a singly linked list L: L0→L1→…→Ln\-1→Ln, reorder it to: L0→Ln→L1→Ln\-1→L2→Ln\-2

红太狼/ 2022年02月04日 23:17/ 0 赞/ 268 阅读