1. 原題鏈接：https://leetcode.com/problems/reorder-list/
2. 解題思路
- 找到中間節點，從中間節點位置斷開，得到兩個鏈表
- 對鏈表的后半截部分進行翻轉
- 將前半截和翻轉后的后半截鏈表進行合并
3. 演算法
- 通過slow、fast指標找到鏈表的中間位置
- 對后半截鏈表進行翻轉操作（注意：后半截鏈表從ceil(n/2)+1位置開始，ceil表示向上取整，整個鏈表從1開始）
- 對兩個鏈表進行合并，因為進行了向上取整，所以前半截鏈表的長度大于等于后半截鏈表
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void reorderList(ListNode* head) {
if(head == NULL || head->next == NULL) return;
//通過slow、fast指標找到鏈表的中間位置
ListNode *slow = head, *fast = head;
while(fast != NULL && fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
}
//對后半截鏈表進行翻轉操作
//注意：后半截鏈表從ceil(n/2)+1位置開始，ceil表示向上取整，整個鏈表從1開始
ListNode *sub_head = slow->next;
sub_head = reverseList(sub_head);
//對兩個鏈表進行合并，因為進行了向上取整，所以前半截鏈表的長度大于等于后半截鏈表
slow->next = NULL;
ListNode *new_head = head;
while(sub_head != NULL){
ListNode *sub_next = sub_head->next;
ListNode *new_next = new_head->next;
sub_head->next = new_head->next;
new_head->next = sub_head;
sub_head = sub_next;
new_head = new_next;
}
}
private:
ListNode* reverseList(ListNode* head){
if(head == NULL || head->next == NULL) return head;
ListNode *n = head->next;
ListNode *new_head = reverseList(head->next);
head->next = n->next;
n->next = head;
return new_head;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85160.html
標籤：其他
上一篇：包含min函式的堆疊
下一篇：堆疊的壓入、彈出序列