题解 | #重排链表#
重排链表
https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=117&tqId=37712&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=&title=
无语，今晚牛客是不是抽风了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return ;
}
// 利用快慢指针移动到中间，翻转后半段链表，然后合并两段链表
ListNode *fast, *slow;
fast = slow = head;
// slow 走到中间位置
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode *pre = nullptr, *cur = slow->next, *nex = slow->next->next;
// 断开链接
slow->next = nullptr;
while (nex) {
cur->next = pre;
pre = cur;
cur = nex;
nex = nex->next;
}
cur->next = pre;
ListNode *head1 = head, *head2 = cur;
while (head1 && head2) {
ListNode *nex1 = head1->next;
ListNode *nex2 = head2->next;
head1->next = head2;
head2->next = nex1;
head1 = nex1;
head2 = nex2;
}
}
};
滴滴公司氛围 330人发布
查看18道真题和解析
投递米哈游等公司6个岗位 >