[c++] Easy solution + explanation | half + reverse + merge
At first we define some basic function len() , at().\n\n len() will return the length of the linked list:\n\tcpp\n\tint len(ListNode* head) {\n\t\tint c = 0;\n\
At first we define some basic function ```len()``` , ```at()```.\n\n* `len()` will return the length of the linked list:\n\t```cpp\n\tint len(ListNode* head) {\n\t\tint c = 0;\n\t\tfor (; head; head = head->next, c++);\n\t\treturn c;\n\t}\n\t```\n* `at()` will give you the address of `i-th` index of a linked list:\n\t```cpp\n\tListNode* at(ListNode* head, int i) {\n\t\tfor (; i--; head = head->next);\n\t\treturn head;\n\t}\n\t```\n* now make a function `half()` that will split the array into half and retun the head of that two list:\n\t```cpp\n\tpair<ListNode*, ListNode*> half(ListNode* head) {\n\t\tif (!head) return {0, 0};\n\t\tListNode *m = at(head, (len(head) - 1) / 2), *y = m->next;\n\t\tm->next = 0;\n\t\treturn {head, y};\n\t}\n\t```\n* make a function `reverse()` that will reverse a linked-list [here i write an easy recursion, the function will return the head and tail of the reversed linked list]:\n\t```cpp\n\tpair<ListNode*, ListNode*> reverse(ListNode* head) {\n\t\tif (!head)return {0, 0};\n\t\tif (!head -> next) return {head, head};\n\t\tauto [x, y] = reverse(head -> next);\n\t\ty -> next = head;\n\t\thead -> next = 0;\n\t\treturn {x, head};\n\t}\n\t```\n* make a `merge()` function to merge two linked list [i.e: x0 -> x1 -> x2 -> ... + y0 -> y1 -> y2 -> ... = x0 -> y0 -> x1 -> y1 -> ...]:\n\t```cpp\n\tListNode* merge(ListNode *x, ListNode *y) {\n\t\tif (!x || !y) return x ? x : y;\n\t\ty = merge(y, x -> next);\n\t\tx -> next = y;\n\t\treturn x;\n\t}\n\t```\n* Now to **reorderList** you can just `half()` + `reverse()` + `merge()` :\n\t``` cpp\n\tvoid reorderList(ListNode* head) {\n\t\tauto [x, y] = half(head);\n\t\ty = reverse(y).first;\n\t\tmerge(x, y);\n\t}\n\t```\n\t\n\t\n\tFull solution:\n\t```cpp\n\t/**\n\t * Definition for singly-linked list.\n\t * struct ListNode {\n\t *     int val;\n\t *     ListNode *next;\n\t *     ListNode() : val(0), next(nullptr) {}\n\t *     ListNode(int x) : val(x), next(nullptr) {}\n\t *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n\t * };\n\t */\n\tclass Solution {\n\t\tint len(ListNode* head) {\n\t\t\tint c = 0;\n\t\t\tfor (; head; head = head->next, c++);\n\t\t\treturn c;\n\t\t}\n\t\tListNode* at(ListNode* head, int i) {\n\t\t\tfor (; i--; head = head->next);\n\t\t\treturn head;\n\t\t}\n\t\tpair<ListNode*, ListNode*> half(ListNode* head) {\n\t\t\tif (!head) return {0, 0};\n\t\t\tListNode *m = at(head, (len(head) - 1) / 2), *y = m->next;\n\t\t\tm->next = 0;\n\t\t\treturn {head, y};\n\t\t}\n\t\tpair<ListNode*, ListNode*> reverse(ListNode* head) {\n\t\t\tif (!head)return {0, 0};\n\t\t\tif (!head -> next) return {head, head};\n\t\t\tauto [x, y] = reverse(head -> next);\n\t\t\ty -> next = head;\n\t\t\thead -> next = 0;\n\t\t\treturn {x, head};\n\t\t}\n\t\tListNode* merge(ListNode *x, ListNode *y) {\n\t\t\tif (!x || !y) return x ? x : y;\n\t\t\ty = merge(y, x -> next);\n\t\t\tx -> next = y;\n\t\t\treturn x;\n\t\t}\n\tpublic:\n\t\tvoid reorderList(ListNode* head) {\n\t\t\tauto [x, y] = half(head);\n\t\t\ty = reverse(y).first;\n\t\t\thead = merge(x, y);\n\t\t}\n\t};\n\t```\n\t\n\t\n\tNow its time to upvote my solution ^_^ \n
['Linked List']