当前位置：首页 > article >正文

力扣143.重排链表

article 2024/10/24 3:09:52

在这里插入图片描述
通过画图分析，可以从反转后链表与原链表中按顺序各自取一个结点来构建结果，不过要注意的这两个链表只会用到一半，结合链表的中间结点和反转链表进行解题。

/**
 * 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:
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    void reorderList(ListNode* head) {
        // 通过画图分析，可以从反转后链表与原链表中按顺序各自取一个结点来构建结果，不过要注意的这两个链表只会用到一半
        // 结合 链表的中间结点 和 反转链表 进行解题

        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid); // 原链表中间位置后面进行反转

        // 问：循环条件 while head2.next 为什么不能写成 while head2？
        // 答：如果链表长度为偶数，例如链表由 [1,2,3,4,5,6] 组成，那么找中间节点 4 并反转后，我们得到的两个链表分别为
        // head=[1,2,3,4] 和 head2=[6,5,4]。注意它俩都包含节点 4，如果写成 while head2，会导致结果中有两个 4
        // 模拟一下head：
        
        // 第一轮 1->6->2 ->3->4
        // 第二轮：1->6->2->5->3 ->4  得出结果，此时head2->next = nullptr，如果还继续循环，那么会得到1->6->2->5->3->4->4
        while (head2->next) {
            ListNode* tmp = head->next;
            ListNode* tmp2 = head2->next;
            head->next = head2;
            head2->next = tmp;
            head = tmp;
            head2 = tmp2;
        }

    }
};