什么是單鏈表的逆置？例如，鏈表a-> B-> C-> D有頭和尾。局部反轉(zhuǎn)是指：a next=&BB->next=&CC->next=&DD->next=0反轉(zhuǎn)后：B->n

什么是單鏈表的逆置？

例如，鏈表a-> B-> C-> D有頭和尾。局部反轉(zhuǎn)是指：a next=&BB->next=&CC->next=&DD->next=0反轉(zhuǎn)后：B->next=&AC->next=&BD->next=&CA->next=0。所謂局部求逆，就是在運(yùn)算中遇到a->next=&B時，重寫為B->next=&a

，即算法的輔助空間為O（1）。其思想是：倒排列表初始為空，依次將列表中的節(jié)點(diǎn)從原列表中“刪除”，然后將倒排列表的頭依次插入（即“頭插入”倒排列表），使其成為倒排列表的第一個“新”節(jié)點(diǎn)，依此類推，直到原列表為空。實(shí)現(xiàn)代碼：void converse（LinkList*head）{LinkList*P，*q P=head->next head->next=null，而（P）{/*向后移動一個位置*/q=P P=P->next/*header plug*/q->next=head->next head->next head->next=q}}