力扣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;//将最后节点的子节点置空
}
};原文地址：https://blog.csdn.net/2301_80505422/article/details/144314699
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！