单向链表的递归反转

我有下面的短代码，这是一个反转链表的问题的解决方案。单向链表的递归反转

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

单向链表的递归反转

回答

相关问题