题目描述
题目链接143. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]
提示：
- 链表的长度范围为
[1, 5 * 104] 1 <= node.val <= 1000
思路解析
利用栈的先入后出的性质，在计算该链表的节点个数的同时，将节点存入栈中，然后在遍历前半段链表的同时，将后半段链表倒序插入前半段链表中。
由于后存入栈中的节点在栈顶，所以我们只需要取栈顶元素即可，插入完成之后将栈顶元素弹出即可。注意在结束遍历时，最后一个节点的子节点需要修改为空。
代码实现
class Solution {
public:void reorderList(ListNode* head) {ListNode*p = head;stack<ListNode*>stk;int cnt=0;while(p){//遍历链表stk.push(p);//将所有节点存入栈中p=p->next;cnt++;//计数}p=head;ListNode* k;for(int i=1;i<=cnt/2;i++){//遍历前半链表stk.top()->next = p->next;//插入链表最后的节点p->next = stk.top();p = stk.top()->next;stk.pop();//插入完成后从栈中删除}p->next = nullptr;//将最后节点的子节点置空}
};
