[LeetCode 第9题] -- Reorder List

题目链接: Reorder List

题目意思: 给的一个链表，要求对链表重新排序。

                例如L0->L1->L2.....->Ln，要求重新排序变成L0->Ln-1->L1->Ln-2->L2....

代码:

/**
 * 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);
};

void Solution::reorderList(ListNode *head) {
    if (NULL == head) {
        return;
    }
    int listCount = 0;
    ListNode* tmpHead = head;
    vector<int> listVal;
    while (tmpHead != NULL) {
        listVal.push_back(tmpHead->val);
        tmpHead = tmpHead->next;
        listCount++;
    }
    tmpHead = head;
    int startToEnd = 0;
    int endToStart = listCount-1; 
    while (tmpHead != NULL) {
        tmpHead->val = listVal[startToEnd++];
        tmpHead = tmpHead->next;
        if (tmpHead != NULL) {
            tmpHead->val = listVal[endToStart--];
            tmpHead = tmpHead->next;
        }
    }
}