【力扣】重排链表

重排链表

代码

class Solution {
public:void reorderList(ListNode* head) {//当链表只有一个节点或两个节点时直接返回空,不用重排if (head->next == NULL || head->next->next == NULL) return;//1. 进行分割链表ListNode* fast = head, *slow = head;ListNode* end1 = NULL;while (fast && fast->next){fast = fast->next->next;end1 = slow;slow = slow->next;}end1->next = NULL;//链表断开，方便合并链表//2. 反转后半部分链表ListNode* prev = NULL, *cur = slow;while (cur){ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}//3. 在原链表上合并两个链表ListNode* cur1 = head->next, *cur2 = prev;ListNode* end = head;//后半部分链表包括了slow指针，后半部分链表节点不会比前半部分链表节点少while (cur2){//先链接后半部分链表，再链接前半部分链表ListNode* next2 = cur2->next;end->next = cur2;end = end->next;cur2 = next2;if (cur1){ListNode* next1 = cur1->next;end->next = cur1;end = end->next;cur1 = next1;}}}
};