Posted on 2014-01-11 02:03
Uriel 閱讀(156)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
這題一開始一直RE，快搞吐了，因為剛切LeetCode，竟然木有看懂掛的那組case是空鏈表的意思...囧rz
這題是要求把
L0→L1→…→Ln-1→Ln這樣的鏈表改為這樣：L0→Ln→L1→Ln-1→L2→Ln-2→…但是不能直接修改鏈表節(jié)點值【也就是說只能改指針
我的方法是DFS遍歷鏈表，設(shè)三個指針，DFS時p1不斷指向next，p2是p1的pre節(jié)點，然后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 };