【快慢指针】LeetCode 143. 重排链表

RomanLin / 2024-11-11 / 原文

题解

用快慢指针先找到中间结点，然后断开前后两条链，用头插法的思路逆转后面那条链，最后两条链依次从前往后遍历插入即可。

参考代码

/**
 * 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 -> next == nullptr) return ;
        ListNode* slow = head, *fast = head -> next;
        while (fast != nullptr && fast -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        fast = slow -> next;
        slow -> next = nullptr;
        slow = head;
        ListNode* h = new ListNode();
        while (fast != nullptr) {
            ListNode* node = fast;
            fast = fast -> next;
            node -> next = h -> next;
            h -> next = node;
        }
        while (h -> next != nullptr) {
            ListNode* node = h -> next;
            h -> next = h-> next -> next;
            node -> next = slow -> next;
            slow -> next = node;
            slow = node -> next;
        }
    }
};