题目表述:将给定的单链表L: L_0→L_1→…→L_{n-1}→L_ nL0→L1→…→Ln−1→Ln
重新排序为:L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L0→Ln→L1→Ln−1→L2→Ln−2→…
要求使用原地算法,不能只改变节点内部的值,需要对实际的节点进行交换。
示例:
输入:{1,2,3,4} 返回值:{1,4,2,3}
给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出
解题思路:首先利用快慢指针,找出链表中间端,将链表一分为二。将后半段链表翻转,再将两个列表依次按序连接即可。
void reorderList(ListNode *head) { //重排链表
if(!head) return ;
//找到中间节点
ListNode *fast,*slow;
fast = head,slow = head;
while (fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
//拆分链表
ListNode *first, *second ;
first = head, second = slow->next;
slow->next = NULL;
//反转链表
ListNode *current,*temp,*newh;
newh = NULL;
current = second;
while (current != NULL)
{
temp = newh;
newh = current;
current = current->next;
newh->next = temp;
}
second = newh;
//合并两个链表
ListNode *first_1,*second_1;
while((first!=NULL)&&(second!=NULL))
{
first_1 = first->next;
second_1 = second->next;
first->next = second;
first = first_1;
second->next = first;
second = second_1;
}
}