【LeetCode】143.重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解题思路：
【【LeetCode】143.重排链表】首先想到的是找到要插入的元素，压入堆栈，弹出时刚好为期望的顺序，然后插入对应位置。
再换一种思路，找到待插入节点的位置，新建一个头结点指向此处，然后将待插入节点反转，最后按顺插入对应节点中。
ListNode* Solution::ReorderList(ListNode *phead)
{
ListNode *p1 = phead;
ListNode *p3 = phead->next;
ListNode *p2 = new ListNode(0);
ListNode *ptemp1;
ListNode *ptemp2;
Solution function;
unsigned int length = 0;
unsigned int devideposition = 0;
unsigned int index = 0;
/*1.get tail length*/
length = function.ListLength(p1);
/*2.check devide position*/
if(length <= 2)
{
return phead;
}
else
{
if(length % 2 == 0)
{
devideposition = length / 2 - 1;
}
else
{
devideposition = length / 2;
}
}
/*3.get p2 head*/
p1 = p1->next;
for(index = 0;
index < length - devideposition;
index ++)
{
p1 = p1->next;
}
p2->next = p1;
/*4.reverse p2*/
p2 = function.ReverseList(p2);
p2 = p2->next;
/*5.insert p2 to p3 by order*/
for(index = 0;
index < devideposition;
index ++)
{
ptemp1 = p3->next;
p3->next = p2;
ptemp2 = p2->next;
p2->next = ptemp1;
p2 = ptemp2;
p3 = ptemp1;
}
p3->next = NULL;
return phead;
}推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长