I know not optimal in time depending on efficiency of uordered_map lookup, but very simple and fast enough.

```
/**
* 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) return;
unordered_map<int, ListNode*> Nodemap;
int i=0, j=0;
Nodemap[i] = head; head = head->next;
while (head){i++; Nodemap[i] = head; head = head->next;}
while (i>j+1){Nodemap[j]->next = Nodemap[i]; j++; Nodemap[i]->next = Nodemap[j]; i--;}
Nodemap[i]->next = NULL;
}
};
```