西安网站建设huanxi/优化设计答案五年级上册

99. 重排链表 

难度系数 中等 通过率 24%

•  描述
•  笔记
•  数据
•  评测

给定一个单链表L: L0→L1→…→Ln-1→Ln,

重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的情况下进行原地操作。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null

 

/*** Definition of ListNode* class ListNode {* public:*     int val;*     ListNode *next;*     ListNode(int val) {*         this->val = val;*         this->next = NULL;*     }* }*/class Solution {
public:/** @param head: The head of linked list.* @return: nothing*/void reorderList(ListNode * head) {// write your code hereif (head == nullptr || head->next == nullptr){return;}ListNode *slow = head, *fast = head->next;while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}fast = slow->next;slow->next = nullptr;ListNode *rHead = nullptr;while (fast){ListNode *r = fast->next;fast->next = rHead;rHead = fast;fast = r;}fast = rHead;slow = head;while(slow&&fast){ListNode *rr = fast->next;ListNode *lr = slow->next;fast->next = lr;slow->next = fast;fast = rr;slow = lr;}}
};