EEPW论坛

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L2→L n-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}

目前能想到的思路就是：先保存整个链表的值到vector中，然后能被2整除的，节点存放v[i]位置

不能被二整除的存放最后的节点。

1. class Solution  

2. {  

3. public:  

4.     void reorderList(ListNode* head)  

5.     {  

6.         if (head==NULL || head->next==NULL)  

7.         {  

8.             return;  

9.         }  

10.   

11.         vector<int> v;  

12.         ListNode* p = head;  

13.         while (p)  

14.         {  

15.             v.push_back(p->val);  

16.             p = p->next;  

17.         }  

18.   

19.         int j = v.size() - 1;  

20.         int i = 0;  

21.         int index = 0;  

22.         p = head;  

23.         while (i<=j)  

24.         {  

25.             if (index%2==0)  

26.             {  

27.                 p->val = v[i];  

28.                 i++;  

29.             }  

30.             else  

31.             {  

32.                 p->val = v[j];  

33.                 j--;  

34.             }  

35.             index++;  

36.             p = p->next;  

37.         }  

38.     }  

39. };