AcWing 3757. 重排链表
原题链接
中等
作者:
小.bug
,
2022-08-10 16:05:44
,
所有人可见
,
阅读 917
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void rearrangedList(ListNode* head) {
//如果是空链表直接返回
if(!head->next) return;
//计算链表长度
int len = 0;
for(auto p = head; p; p = p->next) len ++;
//找到中点(上取整)
int left = (len + 1) / 2;
//将链表从中点一分为二
auto a = head;
for(int i = 0; i < left - 1; i ++) a = a->next;
auto b = a->next, c = a->next->next;
a->next = NULL, b->next = NULL;
//反转链表的后半段
while(c)
{
auto d = c->next;
c->next = b;
b = c, c = d;
}
//合并前后两段
auto p = head, q = b;
while(q)
{
auto o = q->next;
q->next = p->next;
p->next = q;
p = q->next;
q = o;
}
}
};