leetcode-m-Reorder List

143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

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

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Subscribe to see which companies asked this question

• 分析：
  
  • 单链表交换结点位置，肯定浪费时间，于是用空间换取时间。用一个容器记录节点的指针，然后修改next指向即可。
• code

/*** 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==NULL)return ;vector<ListNode*>record;record.push_back(head);while(head->next!=NULL){head=head->next;record.push_back(head);}int size=record.size();//该题是按规律写for(int i=0;i<size/2;i++){if(record[i]->next!=NULL)record[size-i-1]->next=record[i]->next;record[i]->next=record[size-i-1];}//这道题只要把 [] [1] [1,2] [1,2,3]弄明白了就可以record[size/2]->next=NULL;}
};