Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Reorder List-2014.01.06

Posted on 2014-01-11 02:03 Uriel 阅读(139) 评论(0)  编辑 收藏 引用 所属分类: LeetCode
这题一开始一直RE,快搞吐了,因为刚切LeetCode,竟然木有看懂挂的那组case是空链表的意思...囧rz
这题是要求把L0L1→…→Ln-1Ln这样的链表改为这样:L0LnL1Ln-1L2Ln-2→…但是不能直接修改链表节点值【也就是说只能改指针
我的方法是DFS遍历链表,设三个指针,DFS时p1不断指向next,p2是p1的pre节点,然后DFS到链表尾之后每return一次就处理一个,同时p3从头开始向后遍历,这样做完一遍就搞定了~
一开始没明白题意,以为是要输出这样处理之后的链表的值,然后一直TLE,其实是啥也不要输出...=,=
话说C++太弱,LeetCode这样的代码还不是很会,还要多写写...

 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  
10 int cnt, nt;
11 ListNode *p3;
12     
13 class Solution {
14 public:
15     void DFS(ListNode *p1, ListNode *p2) {
16         if(p1->next != NULL) {
17             cnt++;
18             DFS(p1->next, p2->next);
19         }
20         if(nt < cnt) {
21             //cout << p3->val << endl;
22             nt++;
23             if(nt < cnt) {
24                 //cout << p1->val << endl;
25                 nt++;
26             }
27             if(nt == cnt) return;
28             p1->next = p3->next;
29             p2->next = NULL;
30             p3->next = p1;
31             p3 = p3->next->next;
32         }
33     }
34     void reorderList(ListNode *head) {
35         if(head == NULL) return;
36         if(head->next == NULL) {
37             //cout << head->val << endl;
38             return;
39         }
40         p3 = head;
41         cnt = 2;
42         nt = 0;
43         DFS(head->next, head);
44     }
45 };



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理