[LeetCode]143.ReorderList
143. Reorder List
专业从事成都网站制作、成都网站设计,高端网站制作设计,小程序制作,网站推广的成都做网站的公司。优秀技术团队竭力真诚服务,采用H5网站设计+CSS3前端渲染技术,自适应网站建设,让网站在手机、平板、PC、微信下都能呈现。建站过程建立专项小组,与您实时在线互动,随时提供解决方案,畅聊想法和感受。
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}
.
题意:
给定链表L0→L1→…→Ln-1→Ln,重新整理后输出L0→Ln→L1→Ln-1→L2→Ln-2→…链表。
举例如下:给定链表{1,2,3,4,5}重排后为{1,5,2,4,3}
{1,2,3,4,5,6}重排后为{1,6,2,5,3,4}
思路:
1)链表为空,或者链表只有一个或者两个节点,直接返回即可。
2)获取链表的长度len,把链表分成前后两部分。如果长度为奇数,前部分链表长度为len/2 + 1,后部分长度为len/2。比如{1,2,3,4,5}拆分后前部分链表为{1,2,3}后部分链表为{4,5};如果长度为偶数,前部分链表长度为len / 2 ,后部分长度为 len / 2。比如{1,2,3,4,5,6}拆分后为{1,2,3}和{4,5,6}
3)反转第二部分链表。
4)把第二部分链表插入到第一部分链表的指定位置即可。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head) { if ( head == NULL || head->next == NULL || head->next->next == NULL ) { return; } struct ListNode *list = head; int len = 0; while ( list ) { list = list->next; len += 1; } int key = 0; if ( len % 2 == 0 ) { key = len / 2; } else { key = (len / 2) + 1; } struct ListNode *second = head; list = head; int cnt = 0; while ( cnt < key ) { list = second; second = second->next; cnt += 1; } list->next = NULL; list = NULL; struct ListNode *next = NULL; while ( second ) { next = second->next; second->next = list; list = second; second = next; } second = list; next = NULL; while ( second ) { next = second; second = second->next; next->next = head->next; head->next = next; head = head->next->next; } }
网站题目:[LeetCode]143.ReorderList
新闻来源:http://pwwzsj.com/article/jeejgo.html