题解 | #设计LRU缓存结构#
重排链表
http://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if(!head || !head->next) return;
ListNode *fast=head->next, *slow=head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *worker = slow->next;
slow->next = nullptr;
while(worker) {
ListNode *temp=worker->next;
worker->next = slow->next;
slow->next = worker;
worker = temp;
}
ListNode *worker1=head, *worker2=slow->next;
slow->next = nullptr;
while(worker2) {
ListNode *temp = worker2->next;
worker2->next = worker1->next;
worker1->next = worker2;
worker1 = worker2->next;
worker2 = temp;
}
}
};
快慢指针找中点，原地倒序，交叉插入。
投递小天才等公司6个岗位 >
