/** * 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) {        ListNode *first = head, *middle = head, *tail = head, *pre_tail;     if (head == NULL || head->next == NULL) { return;}     pre_tail = middle;     // find the middle node     while (tail != NULL && tail->next != NULL) {         pre_tail = middle;         middle = middle->next;         if (tail->next->next != NULL) {             tail = tail->next->next;         } else {             tail = tail->next;         }     }     ListNode *prev = NULL, *current = middle, *next=middle->next;     while (current != NULL) {         current->next = prev;         prev = current;         current = next;         if (next != NULL) {             next = next->next;         }     }     ListNode *subHead = prev, *subNext = prev;     current = head;     while (current != NULL) {         next = current->next;         current->next = subHead;         current = next;         if (subHead != NULL) {             subNext = subHead->next;             subHead->next = next;             subHead = subNext;         }     }    }};