Open jason89521 opened 3 months ago
Link: https://leetcode.com/problems/reorder-list/description/
Reverse the second half list, then merge the first half list and the reversed list.
/** * 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) {} * }; */ ListNode* reverseList(ListNode* head) { ListNode* cur = head, *prev = nullptr; while (cur != nullptr) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } class Solution { public: void reorderList(ListNode* head) { ListNode* firstTail = head, *fast = head; // find the tail of the second half list while (fast != nullptr) { fast = fast->next; if (fast == nullptr) { break; } fast = fast->next; if (fast == nullptr) { break; } firstTail = firstTail->next; } ListNode* secondHead = firstTail->next; secondHead = reverseList(secondHead); firstTail->next = nullptr; ListNode* temp = secondHead; while (head != nullptr && secondHead != nullptr) { ListNode* firstNext = head->next; ListNode* secondNext = secondHead->next; head->next = secondHead; secondHead->next = firstNext; head = firstNext; secondHead = secondNext; } } };
Time complexity:
Practice Dates
Description
Link: https://leetcode.com/problems/reorder-list/description/
Solution
Reverse the second half list, then merge the first half list and the reversed list.
Performance
Time complexity: