1。利用了栈stack后进先出的性质，存储带 孩子结点 的 结点 的下一个结点.
class Solution{ public: Node* flatten(Node* head) { if(!head) return NULL; Node* p=new Node(); p=head; Node* prehead=p; stack<Node*>ss; while(true) { if(p->child!=NULL) { //当前结点有孩子结点，则记录下来当前结点的下一个结点，用于之后返回来对接 Node* rem=new Node(); rem=p->next; //判断当前结点的下一个结点是不是空的，如果是空的，则说明这个结点是这一层的最后一个，返回的时候直接返回上上一层 if(rem) ss.push(rem); p->next=p->child; p->child->prev=p; //将孩子结点连入结果链表中之后，要把当前结点的孩子结点置位NULL p->child=NULL; p=p->next; } else { //当前结点没有孩子结点， //这一层遍历完了，需要返回上一层啦，利用了stack后进先出的性质，从里往外一层一层的剥开 if(p->next==NULL&&ss.size()>0) { Node *temp=ss.top(); ss.pop(); p->next=temp; temp->prev=p; p=p->next; } //返回到最外面这一层了，且到达最外层的最后一个了，可以跳出结束了。 else if((p->next==NULL&&ss.size()==0)) break; //处在某层的某个中间位置，挨个遍历吧 else p=p->next; } } return prehead; } };
2.
stack
常规DFS遍历，使用stack（LIFO）遍历整个链表
取出每个节点，压入栈内，再按顺序（LIFO）一个个取出，加上两个节点间的关系
记得清空child指针
注意while循环内前两个if语句的顺序，先next的节点，后child节点。(LIFO)
class Solution{ public: Node* flatten(Node* head){ if(!head) return NULL; Node* curr; stack<Node*>stk; stk.push(head); Node *pre=NULL; while(!stk.empty()) { curr=stk.top(); stk.pop(); if(curr->next!=NULL) stk.push(curr->next); if(curr->child!=NULL) { stk.push(curr->child); curr->child=NULL; } if(pre) { pre->next=curr; curr->prev=pre; } pre=curr; } return head; } };
3.递归
递归法
若child为nllptr，将指针移向next节点
若child不为空，进入递归，传入头节点（即，child的第一位）
连接子链表的尾端和父节点的下一节点。
用nextnode记录有child的节点的下一个节点，用来连接在子链表的尾端
通过判断到达链表尾端时，nextnode是否为nullptr，若是，则该尾端就是第一级链表的尾端，若不是，该尾端就是子链表的尾端。（注意使用nextnode连接子链表后，需要将nextnode清空，否则会重复连接子链表）
prevnode用来记录temp的前一个节点，当temp到尾端时为null，这时用prevnode来连接nextnode。
class Solution { public: Node* flatten(Node* head) { Node *temp = head; Node *nextnode = nullptr; Node *prevnode = head; while(prevnode){ if(temp && temp -> child){ nextnode = temp -> next; //记录当前节点的下一个节点 temp -> child -> prev = temp; temp -> next = flatten(temp -> child); //进入递归 temp -> child = nullptr; //注销当前节点的child； } prevnode = temp; //记录null节点的前一个节点 if(temp) temp = temp -> next; if(nextnode && !temp){ //当同一级链表存在下一个节点（即，原来有child的节点的下一节点），且子链表到达null prevnode -> next = nextnode; //连接子节点和之前记录的nextnode所指链表 ---->这一步将其中两级双向链表扁平化 nextnode -> prev = prevnode; temp = prevnode -> next; nextnode = nullptr; //记得清空使用过的nextnode，否则会将无限连接nextnode所指链表 } } return head; }