# [leetcode题解]143. Reorder List(链表重排序)

L:a0->a1->a2->a3…..->an

1.先找到链表的中间节点，然后以中间节点为界将整个链表分成前后两部分。
2.将后半部分链表通过头插的方式进行链表逆置
3.一次交叉插入形成一个新的链表

c++代码如下：

```class Solution {
public:
ListNode *prel = new ListNode(-1);
ListNode *prer = new ListNode(-1);
ListNode *res = new ListNode(-1);

//作者：凌风技术站-iaccepted
//寻找链表的中间节点，并将链表按中间节点一分为二
ListNode *t = half;
half = half->next;
t->next = NULL;

//将链表的后半部分颠倒
while(half != NULL)
{
ListNode *t = half->next;
half->next = prer->next;
prer->next = half;
half = t;
}

//按题目要求交叉连接
ListNode *tail = res;
ListNode *p = prel->next;
ListNode *q = prer->next;
while(p != NULL)
{
tail->next = p;
tail = p;
p = p->next;

tail->next = q;
tail = q;
q = q->next;
}
if (q != NULL)tail->next = q;
else tail->next = NULL;
}

private:
{
while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};```

python代码如下：

```class Solution(object):
"""
:author: 凌风技术站
"""
return
#招链表的中间节点，并将链表一分为二
q = mid.next
mid.next = None

#将后半部分逆置
rq = ListNode(-1)
while q is not None:
t = q.next
q.next = rq.next
rq.next = q
q = t
q = rq.next

#开始交叉合并前后两部分
pre = ListNode(-1)
tail = pre

while q is not None:
tail.next = p
p = p.next
tail = tail.next
tail.next = q
q = q.next
tail = tail.next
if p is not None:
tail.next = p