注意点1：
快慢指针求中间节点，向下取的！！！！
所以我们在循环的时候是需要fast->next fast->next->next
注意点2：
链表反转的时候要返回头节点
此时cur是nullptr 需要返回的是pre
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(!head)return; ListNode* mid = findmid(head); ListNode* l1 = head; ListNode* l2 = mid->next; mid->next = nullptr; l2 = overload(l2); ansnode(l1,l2); } ListNode* findmid(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while(fast->next != nullptr && fast->next->next != nullptr) { fast = fast->next->next; slow = slow->next; } return slow; } ListNode* overload(ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr; while(cur) { ListNode* tmpnode = cur->next; cur->next = pre; pre = cur; cur = tmpnode; } return pre;//pre } void ansnode(ListNode*l1,ListNode* l2) { ListNode* l1next; ListNode* l2next; while(l1 != nullptr && l2 != nullptr) { l1next = l1->next; l2next = l2->next; l1->next = l2; l1 = l1next; l2->next = l1; l2 = l2next; } } };2、除了上面方法还可以直接stl 容器
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head == nullptr)return; vector<ListNode*>vec; ListNode* p = head; int j = 0; int i = 0; while(p) { vec.push_back(p); j++; p = p->next; } j--; while(i < j) { vec[i]->next = vec[j]; vec[j--]->next = vec[++i]; } vec[i]->next = nullptr; } };
