單向鏈表的遞歸反轉

我有下面的短代碼，這是一個反轉鏈表的問題的解決方案。單向鏈表的遞歸反轉

void backwardslist(atom** head) { 
atom* first; 
atom* second; 

if (*head == NULL) return; //if list is empty 

first = *head; 
second = first->next; // intuitive 

if (second == NULL) return; 

backwardslist(&second); // recursive call with 2nd one as head, after we got variables 
        first and second 

first->next->next = first; // when we get to the end, we rearrange it 
first->next = NULL; // so last one is pointing to first, first is pointing to NULL 

*head = second; // I dont understand this part, so the head is changing from the last, 
        to the second element as the recursion goes to the beginning or am i 
        missing something?

}

不是第二=（指向兩個指針在遞歸的第二）？

所以第一次，我明白了，它應該指向最後一個，

但隨着遞歸構建背部，其不斷變化的*頭第二。

第二個atm正在使用什麼？

謝謝你們

來源

2013-08-25 lucija fabijanic

遞歸的原則是：爲空表，用1元 -The第一個元素成爲最後列表 - 它的工作原理-I在列表的其餘部分調用我的函數 – jambono

想到的是遞歸調用你的函數，直至達到最終一個簡單的答案。然後返回最後一個節點。當遞歸函數返回時，設置返回到頭節點的節點的下一個指針。

1) A->B->C->D 
    2) A->B->C->D->C 
    3) A->B->C->D->C->B 
    4) A->B->C->D->C->B->A 
    5)   D->C->B->A->Null

來源

2013-08-25 22:48:00

void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest;

/* empty list */ 
if (*head_ref == NULL) 
    return; 

/* suppose first = {1, 2, 3}, rest = {2, 3} */ 
first = *head_ref; 
rest = first->next; 

/* List has only one node */ 
if (rest == NULL) 
    return; 

/* reverse the rest list and put the first element at the end */ 
recursiveReverse(&rest); 
first->next->next = first; 

/* tricky step -- see the diagram */ 
first->next = NULL;   

/* fix the head pointer */ 
*head_ref = rest;

}

來源

2014-04-19 21:25:18

單向鏈表的遞歸反轉

回答

相關問題