LeetCode 143.Reorder List (重排链表)

拼搏现实的明天。 2022-05-08 13:26 173阅读 0赞

题目描述：

给定一个单链表 *L*：*L*0→*L*1→…→*L**n*\-1→*L*n ，  
将其重新排列后变为： *L*0→*L**n*→*L*1→*L**n*\-1→*L*2→*L**n*\-2→…

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

**示例 1:**

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

**示例 2:**

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

AC C++ Solution:

解题思路：

先将链表对半分为两条链表，将后半段链表倒序，最后再归并两条链表。

代码：

class Solution {
    public:
        void reorderList(ListNode* head) {
            if(!head || !head->next)    return;
            
            //寻找中间节点
            ListNode *p1 = head, *p2 = head->next;
            while(p2 && p2->next) {
                p1 = p1->next;
                p2 = p2->next->next;
            }
            
            //从中间节点切割
            ListNode *head2 = p1->next;
            p1->next = NULL;
            
            //逆序后半段链表
            p2 = head2->next;
            head2->next = NULL;
            
            while(p2) {
                p1 = p2->next;
                p2->next = head2;
                head2 = p2;
                p2 = p1;
            }
            
            //归并两条链表
            for(p1 = head,p2=head2; p1; ) {
                auto t  = p1->next;
                p1->next = p2;
                p1 = p1->next;
                p2 = t;   
            }
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode143 重排链表

![20191205151428958.png][] 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1: 给定链表 1->2->3->4, 重新排

小鱼儿/ 2023年06月19日 09:39/ 0 赞/ 92 阅读

相关 leetcode 143. 重排链表

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

矫情吗；*/ 2023年01月23日 05:51/ 0 赞/ 8 阅读

相关 LeetCode 143. 重排链表 JAVA

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

怼烎@/ 2022年12月16日 13:03/ 0 赞/ 147 阅读

相关【LeetCode 143】重排链表

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

水深无声/ 2022年12月05日 00:47/ 0 赞/ 153 阅读

相关 LeetCode143—Reorder List

原题 [原题链接][Link 1] > Given a singly linked list L: L0→L1→…→Ln-1→Ln, > reorder it to

我不是女神ヾ/ 2022年07月16日 02:21/ 0 赞/ 145 阅读

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

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

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

相关 LeetCode143. 重排链表

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

阳光穿透心脏的1/2处/ 2022年05月10日 04:48/ 0 赞/ 158 阅读

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

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

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

相关 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年03月07日 10:28/ 0 赞/ 140 阅读

相关【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 赞/ 179 阅读