重排链表——力扣143

题目描述

法一：寻找链表中点、链表逆序、链表合并

void reorderList(ListNode* head){if(head==nullptr){return;}// 找到中点 ListNode* mid = FindMiddle(head);ListNode *h1=head, *h2=mid->next;mid->next=nullptr;   // 逆序后半部分h2 = reverseList(h2);// 合并链表mergeList(h1, h2);} ListNode* FindMiddle(ListNode* head){ListNode *slow=head, *fast=head;while(fast->next!=nullptr && fast->next->next!=nullptr){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* head){ListNode* prev=nullptr;ListNode* cur = head;while(cur){ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}void mergeList(ListNode* l1, ListNode* l2){ListNode* l1_tmp;ListNode* l2_tmp;while(l1 && l2){l1_tmp = l1->next;l2_tmp = l2->next;l1->next = l2;l1 = l1_tmp;l2->next = l1;l2 = l2_tmp;}}