Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
思路：
先把链表分成两节，后半部分翻转，然后前后交叉连接。
大神的代码比我的简洁，注意分两节时用快慢指针。
大神巧妙的在最后一步融合时用了连等号
在翻转部分：大神翻转过的部分的结尾是null. 而我的方法是把结尾连接下一个待翻转的结点。
// O(N) time, O(1) space in total
void reorderList(ListNode *head) {
if (!head || !head->next) return; // find the middle node: O(n)
ListNode *p1 = head, *p2 = head->next;
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
} // cut from the middle and reverse the second half: O(n)
ListNode *head2 = p1->next;
p1->next = NULL; p2 = head2->next;
head2->next = NULL;
while (p2) {
p1 = p2->next;
p2->next = head2;
head2 = p2;
p2 = p1;
} // merge two lists: O(n)
for (p1 = head, p2 = head2; p1; ) {
auto t = p1->next;
p1 = p1->next = p2;
p2 = t;
}
}
我的代码
void reorderList(ListNode *head) {
int len = ; //链表长度
ListNode * p = head;
ListNode * latterpart = head;
//找链表长度
while(p != NULL)
{
len++;
p = p->next;
}
if(len <= )
{
return;
}
//把链表分成两份 如1 2 3 4 5 分成 1 2 3 和 4 5
len = (len + ) / ; //一半的位置
p = head;
while(--len)
{
p = p->next;
}
latterpart = p->next;
p->next = NULL;
//翻转后半部分
ListNode * plast = latterpart;
while(plast->next != NULL)
{
p = plast->next;
plast->next = p->next;
p->next = latterpart;
latterpart = p; //更新头部 每次把后面的转到最前面去
}
//交叉前后两段
p = head;
while(p != NULL && latterpart != NULL) //如果前半部分和后半部分都还有可连接的 继续
{
ListNode * tmp = p->next;
p->next = latterpart;
latterpart = latterpart->next;
p->next->next = tmp;
p = p->next->next;
}
return;
}