[LeetCode] Reorder List

Given a singly linked list L: , reorder it to:

You must do this in-place without altering the nodes’ values.

For example, Given .

解题思路1

首先用一个vector存储所有的结点，然后将倒数第i个结点插入到第i个结点之后。

实现代码1;struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL){}};class Solution {public:void reorderList(ListNode *head) {if (head == NULL){return;}ListNode *p = head;vector<ListNode*> nodes;while (p){nodes.push_back(p);p = p->next;}int left = 0;int right = nodes.size() – 1;while (left < right){nodes[left]->next = nodes[right];nodes[right–]->next = nodes[++left];}nodes[left]->next = NULL;}};int main(){ListNode *p1 = new ListNode(1);ListNode *p2 = new ListNode(2);ListNode *p3 = new ListNode(3);ListNode *p4 = new ListNode(4);p1->next = p2;p2->next = p3;p3->next = p4;Solution s;s.reorderList(p1);ListNode *p = p1;while (p){cout<<p->val<<endl;p = p->next;}}解题思路2

首先把链表从中间分成两部分，然后将后一部分链表反转，最后将两个链表合并。

实现代码2//Runtime:98 msclass Solution {public:void reorderList(ListNode *head) {if (head == NULL){return;}ListNode* ps = head;ListNode* pf = head;while (pf->next && pf->next->next){ps = ps->next;pf = pf->next->next;}ListNode *p2 = ps->next;ps->next = NULL;p2 = reverseList(p2);head = mergeList(head, p2);}ListNode* mergeList(ListNode *p1, ListNode *p2){ListNode *result = p1;ListNode *temp;while (p2){temp = p2;p2 = p2->next;temp->next = p1->next;p1->next = temp;p1 = p1->next->next;}return result;}ListNode* reverseList(ListNode *head){if (head == NULL){return NULL;}ListNode *p = head->next;head->next = NULL;while (p){ListNode *temp = p;p = p->next;temp->next = head;head = temp;}return head;}};

，每一天都不可追回，所以更要珍惜每一寸光阴，