Posted on 2014-01-11 02:03
Uriel 阅读(136)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
这题一开始一直RE，快搞吐了，因为刚切LeetCode，竟然木有看懂挂的那组case是空链表的意思...囧rz
这题是要求把
L0→L1→…→Ln-1→Ln这样的链表改为这样：L0→Ln→L1→Ln-1→L2→Ln-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 };