网站的收录率,便民工具 网站开发,wordpress 网页存在哪里,建网站哪家好新闻题干
LCR 026. 重排链表
给定一个单链表 L 的头节点 head #xff0c;单链表 L 表示为#xff1a; L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为#xff1a;
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值#xff0c;而是需要实…题干
LCR 026. 重排链表
给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 解法寻找链表中点 链表逆序 合并链表
/*** 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:// 获取链表的中间节点ListNode *getMid(ListNode* head) {ListNode* fast head;ListNode* slow head;while (fast ! nullptr fast-next ! nullptr) {fast fast-next-next;slow slow-next;}return slow;}// 反转链表ListNode *revers(ListNode* head) {ListNode *pre nullptr;ListNode *curr head;while (curr ! nullptr) {ListNode *next curr-next;curr-next pre;pre curr;curr next;}return pre;}// 合并两个链表void merge(ListNode *l1, ListNode *l2) {ListNode *l1_tmp;ListNode *l2_tmp;while (l1 ! nullptr l2 ! nullptr) {l1_tmp l1-next;l2_tmp l2-next;l1-next l2;l1 l1_tmp;l2-next l1;l2 l2_tmp;}}// 重新排序链表void reorderList(ListNode* head) {if (head nullptr || head-next nullptr) {return;}ListNode* mid getMid(head);ListNode *rightHead mid-next;mid-next nullptr;ListNode *reversedRight revers(rightHead);merge(head, reversedRight);}
};
解析
这道题综合了前几道题比较基础的算法正好可以用来复习。
1.找到原链表的中点参考「876. 链表的中间结点」。 2.将原链表的右半端反转参考「206. 反转链表」。 3.合并两个链表。
