143. Reorder List
1. Description
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
2. Example
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
3. Constraints
- The number of nodes in the list is in the range [1, $5 * 10^4$].
- 1 <= Node.val <= 1000
4. Follow Up
- Recursive solution is trivial, could you do it iteratively?
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(1)
// 1. find the middle point of the list
// 2. reverse the right half list
// 3. reconstruct the list
class Solution {
public:
// void reorderList(ListNode *head)
void reorderList(ListNode *m_head) {
auto middleNode = findMiddleNode(m_head);
auto reversedRightHalfList = reverseList(middleNode->next);
middleNode->next = nullptr;
auto guardHead = new ListNode();
auto iter = guardHead, left = m_head, right = reversedRightHalfList;
while (right) {
iter->next = left;
left = left->next;
iter = iter->next;
iter->next = right;
right = right->next;
iter = iter->next;
}
iter->next = left;
m_head = guardHead->next;
}
private:
ListNode *findMiddleNode(ListNode *i_head) {
auto guardHead = new ListNode();
guardHead->next = i_head;
auto slow = guardHead, fast = guardHead;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode *reverseList(ListNode *m_head) {
if (!m_head) {
return nullptr;
}
auto lastReversedIter = m_head, firstUnreversedIter = m_head->next;
lastReversedIter->next = nullptr;
while (firstUnreversedIter) {
auto nextNode = firstUnreversedIter->next;
firstUnreversedIter->next = lastReversedIter;
lastReversedIter = firstUnreversedIter;
firstUnreversedIter = nextNode;
}
return lastReversedIter;
}
};