描述
給定一個單鏈表L：L0->L1->....->Ln-1->Ln，重新排列鏈表為這樣的順序：L0->Ln->L1->Ln-1....
使用原地操作，不可以修改節(jié)點的值；
分析
這道題目可以分為三部分：
1，找到單鏈表的中間節(jié)點费坊，從此斷開，將鏈表分為前旬痹、后兩部分附井；
2，將后半部分單鏈表逆轉两残；
3永毅，將前后兩個鏈表合并；
實現(xiàn)
//Reorder List
ListNode *reorderList(ListNode *head)
{
ListNode *middle = findTheMiddleNode(head);
ListNode *list2 = middle->next;
ListNode *cur = head;
middle->next = nullptr;
// 逆轉list2
list2 = reverseWithHeadNode(list2);
//依次插入list1 list2
while (cur->next) {
ListNode *next1 = cur->next;
cur->next = list2;
list2 = list2->next;
cur->next->next = next1;
cur = next1;
}
cur->next = list2;
return head;
}
// Find the middle node
ListNode *findTheMiddleNode(ListNode *head)
{
ListNode *slow = head;
ListNode *fast = head;
ListNode *middle = nullptr;
while (fast && fast->next) {
middle = slow;
slow = slow->next;
fast = fast->next->next;
}
return middle;
}
// reverse just with head node
ListNode *reverseWithHeadNode(ListNode *head)
{
ListNode *prev = head;
ListNode *cur = head->next;
ListNode *next = cur->next;
while (cur) {
cur->next = prev;
//移動指針
prev = cur;
cur = next;
next = next?next->next:nullptr;
}
head->next = nullptr;
return prev;
}
此算法的時間復雜度為O(n)人弓，空間復雜度為O(1)沼死。
