当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--72--重排链表（C语言）
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
（题目来源：力扣（LeetCode））
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
1.寻找链表中点 + 链表逆序 + 合并链表
void reorderList(struct ListNode* head){
if(head==NULL||head->next==NULL){//排除链表为空和长度为1的情况
return;
}
struct ListNode* index1=head;//指针1
struct ListNode* index2=head->next;//指针2
while(index2->next!=NULL){//寻找中间结点
index1=index1->next;
index2=index2->next;
if(index2->next!=NULL) index2=index2->next;
}
index2=index1->next;//后一段的头结点
index1->next=NULL;// 将链表断开成两个链表，第一个链表置为NULL
struct ListNode* nex;//辅助指针
while(index2!=NULL){//逆置第二个链表
nex=index2->next;
index2->next=index1->next;
index1->next=index2;
index2=nex;
}
struct ListNode* s=head;//指向第一个链表的指针
index2=index1->next;//指向第二个链表
index1->next=NULL;//第一个链表尾置NULL
while(index2!=NULL){//将第二个链表依次插入第一个链表指定位置
nex=index2->next;
index2->next=s->next;
s->next=index2;
s=index2->next;
index2=nex;
}
}
