题解 | #重排链表#
重排链表
http://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b
将len/2后的节点单独拿出来为l2链表，len/2前的链表为l1链表。然后合并两个链表即可。细节真多啊。。。
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) return;
int len = 0;
ListNode* tmp_head = head;
ListNode* tail = nullptr;
ListNode* tmp = nullptr;
ListNode* l1 = nullptr, * l2 = nullptr;
while (head)
{
head = head->next;
len++;
}
if (len <= 2) return;
head = tmp_head;
int i = 1;
while (i < len / 2)
{
head = head->next;
i++;
}
if (len % 2 == 1)
{
head = head->next;
tail = head;
tmp = head->next;
head->next = nullptr;
}
else
{
tail = head;
tmp = head->next;
head->next = nullptr;
}
l2 = backList(tmp);
l1 = tmp_head;
i = 0;
while (i < len / 2)
{
auto l1_next = l1->next;
auto l2_next = l2->next;
l1->next = l2;
l2->next = l1_next;
l1 = l1_next;
l2 = l2_next;
i++;
}
l1 = tmp_head;
}
//链表反转
ListNode* backList(ListNode* head)
{
ListNode* new_head = nullptr;
ListNode* tmp = nullptr;
if (!head || !head->next) return head;
while (head)
{
tmp = head;
head = head->next;
tmp->next = new_head;
new_head = tmp;
}
return new_head;
}
};
