这个题是三合一:找链表中间节点+反转链表+合并链表。
class Solution {
public:
ListNode* findMiddle(ListNode* head) //快慢指针找链表中点
{
auto fast = head, slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* reverse(ListNode* head) //反转链表
{
if (head == nullptr) return nullptr;
auto pre = head, cur = head->next;
while (cur)
{
auto ne = cur->next;
cur->next = pre;
pre = cur, cur = ne;
}
head->next = nullptr;
return pre;
}
void merge(ListNode* L1, ListNode* L2) //合并链表
{
while (L1 && L2)
{
auto p1 = L1->next, p2 = L2->next;
L1->next = L2;
L1 = p1; //L1往下走一步,即L1 = L1->next
L2->next = L1;
L2 = p2; //L2往下走一步,即L2 = L2->next
}
}
void reorderList(ListNode* head) {
if (head == nullptr) return;
auto mid = findMiddle(head);
auto L1 = head, L2 = mid->next;
mid->next = nullptr; //中点后截断,分成两条链表
L2 = reverse(L2);
merge(L1, L2);
}
};