图解:
/**
* 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 n = 0;
//求出链表长度n
for(auto p = head; p ; p = p->next) n ++;
//从中间上取整一分为二,求出前半截结点的数目left
int left = (n + 1) / 2;
//遍历前半截结点,用指针指向后半段的首结点b,次结点c(便于遍历后半段)
auto a = head;
for(int i = 0;i < left - 1;i ++) a = a->next;
auto b = a->next, c = b->next;
//两段都断开
a->next = b->next = NULL;
//反转后半段链表
while(c)
{
auto p = c->next;
c->next = b;
b = c, c = p;
}
//合并两段链表
auto p = head, q = b;
while(q)
{
auto o = q->next;
q->next = p->next;
p->next = q;
p = q->next;
q = o;
}
}
};
想提高链表能力,推荐刷题:
https://www.acwing.com/problem/content/33/
https://www.acwing.com/problem/content/34/
https://www.acwing.com/problem/content/86/
https://www.acwing.com/problem/content/1453/