https://leetcode.com/problems/reorder-list/
/** * 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 or head->next == nullptr) return ; ListNode* slow=head,*fast=head,*prev; // 这个地方是 and while(fast and fast->next ){ prev = slow; slow = slow->next; // cout<<slow->val<<endl; fast = fast->next->next; } // 这个找中点的方法，均分或者 后面多一个。 ListNode* slow2; prev->next = nullptr; ListNode* s = head; while(s){cout<<s->val<<endl;s=s->next;} slow2 = rev(slow); // ListNode* s = slow2; // while(s){cout<<s->val<<endl;s=s->next;} head = merge3(head,slow2); return ; } ListNode* rev(ListNode* h){ ListNode* prev =nullptr,*cur = h,*nxt; if(cur == nullptr or nxt == nullptr) return h; while(cur != nullptr){ // cout<<cur->val<<endl; nxt = cur->next; cur->next=prev; prev = cur; cur = nxt; // cur = cur->next; } // 这里不知道为什么不可以用赋值指针的形式来，head = prev。会出错。 return prev ; } // void merge(ListNode* h,ListNode* e){ // if(h == nullptr or e == nullptr) return ; // ListNode* cur = h; // // *havf = e,*nxt; // while(cur != nullptr){ // // cout<<cur->val<<endl; // ListNode* nxt = cur->next; // ListNode* havf = e->next; // cur->next = e; // cout<<cur->val<<endl; // if(nxt = nullptr) break; // e->next = nxt; // // cout<<nxt->val<<endl; // cur = nxt; // e=havf; // // cur->next = havf; // // // if(cur == nullptr) break; // // havf = havf->next; // // cout<<havf->val<<endl; // // cur = cur->next; // // cur->next = nxt; // // cur=cur->next; // } // // if(havf != nullptr) cur->next = havf; // return ; // } ListNode* merge2(ListNode* l1,ListNode* l2){ if(!l1) return l2 ; if(!l2) return l1 ; l1->next = merge2(l2,l1->next); return l1; } ListNode* merge3(ListNode* l1,ListNode* l2){ ListNode *n1,*n2; ListNode* h = l1; while(l1){ n1 = l1->next; n2 = l2->next; l1->next = l2; if(!n1) break; // 靠这个中断来留住下面长的list的小尾巴。 l2->next = n1; l1 = n1; l2 = n2; } return h; } };主要思路是：把链表中间分开来，然后反转后面一半，在合并两个链表。
自己一开始是想把链表单独反转一份，然后，重新合成一个。这样有点浪费空间，需要思考空间的浪费程度。
