LeetCode| Reorder List 重新排序链表
题目:
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}
.
#include <iostream> #include <vector> using namespace std; /* 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}. */ typedef struct list_node List; struct list_node { struct list_node* next; int value; }; void print_list(List* list) { List* tmp=list; while(tmp != NULL) { cout<<tmp->value<<endl; tmp = tmp->next; } } /* 初始化List 将从1~n的数字插入到链表中 */ void Init_List(List*& head,int* array,int n) { head = NULL; List* tmp; List* record; for(int i=1;i<=n;i++) { tmp = new List; tmp->next = NULL; tmp->value = array[i-1]; if(head == NULL) { head = tmp; record = head; } else { record->next = tmp; record = tmp; } } } int Len_list(List* list) { if(list == NULL) return 0; else return Len_list(list->next)+1; } /* 重新排序链表 将一个链表拆分 然后再重新组合 具体的情况也得分析来看 如果节点数目是偶数个 那么正好平分 然后将后一半的链表反转 之后就可以插入了 如果节点数据是奇数个 那么前半部多一个 然后后半部反转 之后进行插入 */ /* 链表的反转 */ void Reverse(List*& list) { List* tmp = NULL; List* cur = list; List* next = list->next; while(next != NULL) { cur->next = tmp; tmp = cur; cur = next; next = next->next; } cur->next = tmp; list = cur; } void Reorder_list(List*& list) { List* first = list; List* second; List* tmp_first,*tmp_second; int len = Len_list(first); int i; if(len%2 == 0) { for(i=1;i<len/2;i++) first = first->next; } else { for(i=1;i<(len/2)+1;i++) first = first->next; } second = first->next; first->next = NULL; Reverse(second); first = list; // 开始进行融合 首先可以保证的是second链表的个数肯定不会比first链表的节点数目多 while(second != NULL) { tmp_first = first->next; tmp_second = second->next; first->next = second; second->next = tmp_first; second = tmp_second; first= tmp_first; } } int main() { int array[]={1,2,3,4,5,6,7,8,9,10,11,12}; List* head; Init_List(head,array,sizeof(array)/sizeof(array[0])); Reorder_list(head); print_list(head); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。