admin 管理员组文章数量: 1087649
Reorder List
题目大意
好吧,这题之前看错题目了,以为是按照奇偶依次提取然后将偶序列倒序后插入奇序列,那写得我叫一个纠结,后来仔细读了一遍题目才发现不是酱紫。。题目大意是将一个链表的后半段倒序后依次插入前半段的空格中,简单粗暴。
思路
显然解法也是简单粗暴,顺序就是:截取后半段->倒序->插入前半段,详见代码
总结
看题得仔细,另外插入时注意对空结点的处理
代码
[cpp] view plain copy print ?
- /**
- * Definition for singly-linked list.
- * struct ListNode {
- * int val;
- * ListNode *next;
- * ListNode(int x) : val(x), next(NULL) {}
- * };
- */
- class Solution {
- public:
- ListNode *reverse(ListNode *cur, ListNode *fa)//翻转链表
- {
- if (cur == NULL)return fa;
- ListNode *temp = reverse(cur->next, cur);
- cur->next = fa;
- return temp;
- }
- void reorderList(ListNode *head)
- {
- if (head == NULL)return ;
- ListNode *headE, *headO, *f_p, *s_p;
- f_p = s_p = headE = headO = head;//快慢指针
- int count = 0;
- while (f_p->next != NULL){
- if (count % 2)s_p = s_p -> next;
- f_p = f_p -> next;
- count ++;
- }
- headO = s_p->next;//后半段序列的头
- s_p->next = NULL;//断链
- headO = reverse(headO, NULL);//翻转
- ListNode *odd = headO;
- ListNode *even = headE;
- while (odd != NULL || even != NULL){//插入
- ListNode *tmp = even;
- if (even != NULL) even = even->next;
- if (odd != NULL) tmp->next = odd;
- tmp = odd;
- if (odd != NULL) odd = odd-> next;
- if (even != NULL) tmp->next = even;
- }
- }
- };
本文标签: Reorder List
版权声明:本文标题:Reorder List 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.roclinux.cn/p/1700324125a397074.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论