?LeetCode刷題實戰(zhàn)430：扁平化多級雙向鏈表

class?Solution?{
public:
????Node* flatten(Node* head) {
????????Node *cur = head, *nextNode = NULL, *prevN = head;
????????//所有的指針記得初始化，不要以為后面要付值就不要初始值，怕后面if沒進去
????????while(prevN)
????????{ //遍歷鏈表
????????????if(cur && cur->child) //當前有，且有子鏈
????????????{
????????????????nextNode = cur->next;//記住上層cur后面的
????????????????cur->next = flatten(cur->child);//展平
????????????????cur->child->prev = cur;//子鏈頭接上，展平
????????????????cur->child = NULL;//將cur孩子刪掉
????????????}
????????????prevN = cur;//prevnode移動
????????????if(cur)
????????????????cur = cur->next;//cur移動
????????????if(!cur && nextNode)
????????????{ //當cur到終點的下一個時，且上層后面還有nextnode
????????????????prevN->next = nextNode;//展平的終點prevN指向上層的nextnode
????????????????nextNode->prev = prevN;//反向接上
????????????????cur = prevN->next;//cur移動
????????????????nextNode = NULL;//已接好，暫時沒有child的需要展平，nextNode清空
????????????}
????????}
????????return?head;
????}
};