找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1080|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Reorder List】-【刷题第一弹】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 11-27-2014 02:24 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:
https://oj.leetcode.com/problems/reorder-list/

题目:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,  reorder it to: L0→LnL1→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}.



建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                          汇总贴 传送门
==================================

本帖被以下淘专辑推荐:

发表于 11-27-2014 01:40 PM | 显示全部楼层
思路:拆一半,翻转,再拼接
代码:
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. *     int val;
  5. *     ListNode *next;
  6. *     ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11.     ListNode * reverse(ListNode *head) {
  12.         ListNode *temp = head->next;
  13.         head->next = 0;
  14.         while (temp) {
  15.             ListNode *next = temp->next;
  16.             temp->next = head;
  17.             head = temp;
  18.             temp = next;
  19.         }
  20.         return head;
  21.     }
  22.     void merge(ListNode *head1,ListNode *head2) {
  23.         ListNode *tail = head1;
  24.         head1 = head1->next;
  25.         for (;head1 || head2;) {
  26.             if (head2) {
  27.                 tail = tail->next = head2;
  28.                 head2 = head2->next;
  29.             }
  30.             if (head1) {
  31.                 tail = tail->next = head1;
  32.                 head1 = head1->next;
  33.             }
  34.             
  35.         }
  36.     }
  37.   
  38.     void reorderList(ListNode *head) {
  39.         // IMPORTANT: Please reset any member data you declared, as
  40.         // the same Solution instance will be reused for each test case.
  41.         ListNode *temp = head;
  42.         int length = 0;
  43.         for (; temp; ++length, temp = temp->next)
  44.         ;
  45.         if (length <= 2) {
  46.             return;
  47.         }
  48.         
  49.         temp = head;
  50.         for (length = (length - 1) >> 1; length; --length,temp = temp->next)
  51.         ;
  52.         ListNode *head2 = temp->next;
  53.         temp->next = 0;
  54.         head2 = reverse(head2);
  55.         merge(head, head2);
  56.       
  57.    
  58.         
  59.     }
  60. };
复制代码

复杂度分析:O(N)
细节和陷阱:注意空指针,长度的奇偶性等。拼接也可能后一段是空的。可以用哨兵,但我不喜欢没事多加个节点,主要是要涉及到new/delete....
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 1-24-2015 08:18 AM | 显示全部楼层
  1.         ListNode dummy(-1);
  2.         dummy.next = head;
  3.         
  4.         ListNode *fast = &dummy, *slow = &dummy;
  5.         for( ; fast && fast->next; fast = fast->next->next){
  6.             slow = slow->next;
  7.         }
复制代码

按这种方式得到的slow指针,无论链表的长度是奇数还是偶数,slow->next都是需要翻转的链表的头结点,不需要求长度
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表