欢迎访问LeetCode题解合集

题目描述

给定一个单链表 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.

题解：

• 使用快慢指针将链表从中间节点分为左右两部分
• 将右部分链表原地逆序
• 将两部分链表的节点依次交叉连接

时间复杂度：$O(n)$

额外空间复杂度：$O(1)$

/**
 * 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 || !head->next || !head->next->next )
            return;

        ListNode *s = head, *f = head->next;
        while ( true ) {
            if ( !f || !f->next ) break;
            f = f->next->next;
            s = s->next;
        }

        ListNode *right_head = s->next;
        s->next = nullptr;

        ListNode *pre = nullptr, *nxt = nullptr;
        while ( right_head ) {
            nxt = right_head->next;
            right_head->next = pre;
            pre = right_head;
            right_head = nxt;
        }
        right_head = pre;

        pre = head;
        s = head->next;
        while ( s || right_head ) {
            if ( right_head ) {
                pre->next = right_head;
                right_head = right_head->next;
                pre = pre->next;
            }
            if ( s ) {
                pre->next = s;
                s = s->next;
                pre = pre->next;
            }
        }
    }
};
/*
时间：44ms，击败：94.59%
内存：17.1MB，击败：99.72%
*/