Leetcode 430.扁平化多级双向链表
2024-09-04 09:58:36
扁平化多级双向链表
您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示。
扁平化列表,使所有结点出现在单级双链表中。您将获得列表第一级的头部。
示例:
输入:
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
输出:
1-2-3-7-8-11-12-9-10-4-5-6-NULL
以上示例的说明:
给出以下多级双向链表:
我们应该返回如下所示的扁平双向链表:
思路:这道题直接用栈就阔以搞定,分三种情况:
1:如果当前节点有孩子节点,把当前节点的下一个节点放入栈中,并且把当前节点的孩子节点指向当前节点的下一个节点
2:否则如果当前节点的下一个节点为空且栈不为空(已经处理完所有的带孩子节点的节点,现在已经到了孩子节点的最后一个节点),那么显而易见的根据题意我们需要把孩子节点的最后一个节点指向当前节点。
3:每次都更新当前节点为下一个节点
import java.util.Stack; // Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child; public Node() {} public Node(int _val,Node _prev,Node _next,Node _child) {
val = _val;
prev = _prev;
next = _next;
child = _child;
}
}; class Solution {
public Node flatten(Node head) {
if(head==null) return head;
Node p=head;
Stack<Node> s=new Stack<Node>();
while(p!=null){
if(p.child!=null){
s.push(p.next);
p.next=p.child;
if(p.next!=null) p.next.prev=p;
p.child=null;
}else if(p.next==null&&!s.empty()){
p.next=s.pop();
if(p.next!=null) p.next.prev=p;
}
p=p.next;
}
return head;
}
}
最新文章
- php请求返回GeoJSON格式的数据
- efwplus框架介绍
- Zygote(app_process)相关分析2
- Dell商用台式机、笔记本、服务器800电话
- IE css expression(表达式)
- android中使用Intent在activity之间传递数据
- asp.net中利用session对象传递、共享数据[session用法]
- vb的property 和event
- 11.巨坑,注意了,关于显示不正常的问题,localstorage的存储问题
- Strom数据流分组解析
- Unity配置安卓开发环境
- 分享一个基于web的满意度调查问卷源码系统
- Maven项目在更新过程停止,再更新无效-->;解决
- 转:C#线程系列讲座(1) BeginInvoke和EndInvoke方法
- new int
- 在SELECT的时候,加入一列固定值
- phpmyadmin 各种技巧拿 webshell
- 0ctf2018 pwn
- netty5入门教程
- layui——上传图片,并实现放大预览