南浔区住房和城乡建设局网站,WordPress电影评分模板,龙岩特色,抖音生活服务旅行社ota入驻复杂链表的复制
题目#xff1a;实现一个函数complexListNode 复制一个复杂链表。在链表中#xff0c;每个节点除了有一个next指针指向下一个节点#xff0c;还有另外一个before节点#xff0c;before节点指向链表中任意一个节点#xff0c;或者null节点。链表节点定义使…复杂链表的复制
题目实现一个函数complexListNode 复制一个复杂链表。在链表中每个节点除了有一个next指针指向下一个节点还有另外一个before节点before节点指向链表中任意一个节点或者null节点。链表节点定义使用之前文章 数据结构与算法–链表实现以及应用 中链表节点的定义以及链表中其他方法实现都沿用以上文章中有详细的说明。如下节点定义
public class ListNode implements ComparableListNode {private Integer value;private ListNode next;private ListNode before;
......
}如下图中包含的5个阶段的复杂链表图中实线箭头表示next指针虚线表示before指针简单画出如下我们省略了null指针没有画出来 分析 方法一如上链表的结构看最简单的方式先遍历一次将节点复制并且用next 链接节点得到基础结构在循环查找每一个节点的before节点因为此处before节点是随机指向可能指向本节点之前的节点因此每次都需要遍历一次链表来查找对应的节点信息时间复杂度O(N2)方法二为了避免before节点查找的复杂性先遍历一次oldList复制next指针并且将oldNodenewNode存储到map中第二次遍历此时我们已经知道了oldNode~ newNode的对应关系我们在查找到oldList的before指向的时候直接从map中获取到对应newNode这样通过O1 时间获取到before的值此处空间换时间的方法方法三换一种思路能否不用辅助空间情况下来实现O(n)的时间复杂度第一次遍历直接将访问到的节点复制新节点并且插入到访问到的节点后面如下图 第二次遍历设置新建节点的before节点因为每个新节点A‘都在老节点A的next位置所以老节点A 的before C节点的next 就是改节点的新节点C’ 那么新节点A‘ 的before节点就是 C’第三次遍历将奇数项的节点单独拆分成一个链表得到我们复制的链表偶数位项就是老的链表 根据如上分析有如下代码
/*** 构建复杂链表链表next节点指向下一个节点* before节点指向链表中任意节点* */public static ListNode buildComplexListNode(){Random random new Random();ListNode pHead new ListNode(random.nextInt(100));ListNode[] nodeArray new ListNode[20];for (int i 0; i 20; i) {ListNode newNode new ListNode(random.nextInt(100));nodeArray[i] newNode;ListNode headNode pHead;while (headNode.getNext() ! null){headNode headNode.getNext();}headNode.setNext(newNode);}print(pHead);ListNode headNode pHead;while (headNode.getNext() ! null){headNode.setBefore(nodeArray[random.nextInt(nodeArray.length -1)]);headNode headNode.getNext();}return pHead;}/*** 复制复杂链表* 方法一空间换时间* 先遍历一次oldList复制next指针并且将oldNodenewNode存储到map中* 第二次遍历同时遍历oldListnewList直接通过oldList的before指向的oldListNode从mep中获取newNode* O(1)时间获取到before值* */public static ListNode complexListNode(ListNode pHead){if(pHead null || pHead.getNext() null){return pHead;}MapListNode, ListNode oldToNewNode new HashMap();ListNode complexNode pHead;ListNode newHead null;ListNode myHeadNode null;while (complexNode ! null){ListNode createNode new ListNode(complexNode.getValue());oldToNewNode.put(complexNode, createNode);if(newHead null){newHead createNode;myHeadNode newHead;}else {myHeadNode.setNext(createNode);myHeadNode myHeadNode.getNext();}complexNode complexNode.getNext();}ListNode beforeComplexNode pHead;ListNode beforeSetNode newHead;while (beforeComplexNode.getNext() ! null beforeSetNode.getNext() ! null){if(oldToNewNode.containsKey(beforeComplexNode.getBefore())){beforeSetNode.setBefore(oldToNewNode.get(beforeComplexNode.getBefore()));}beforeComplexNode beforeComplexNode.getNext();beforeSetNode beforeSetNode.getNext();}return newHead;}
/*** 复制复杂链表* 方法二* 第一次遍历直接将范问到的节点复制新节点并且插入到范问到的节点后面* 第二次遍历设置新建节点的before节点因为每个新节点A‘都在老节点A的next位置所以老节点的before B节点的next 就是改节点的新节点B’* 那么新节点A‘的before节点就是B’* 第三次遍历将奇数项的节点单独拆分成一个链表得到我们复制的链表偶数位项就是老的链表*/public static ListNode complexListNode_2(ListNode pHead){if(pHead null || pHead.getNext() null){return pHead;}ListNode compleNode pHead;while (compleNode.getNext() ! null){ListNode createNode new ListNode(compleNode.getValue());createNode.setNext(compleNode.getNext());compleNode.setNext(createNode);compleNode compleNode.getNext().getNext();}ListNode beforeCompleNode pHead;while (beforeCompleNode.getNext() ! null){if(beforeCompleNode.getBefore() ! null){beforeCompleNode.getNext().setBefore(beforeCompleNode.getBefore().getNext());}beforeCompleNode beforeCompleNode.getNext().getNext();}ListNode fixCompleNode pHead;ListNode resultHead null;ListNode resultNode null;while (fixCompleNode.getNext() ! null){if(resultHead null){resultHead fixCompleNode.getNext();resultNode resultHead;}else {resultNode.setNext(fixCompleNode.getNext());resultNode resultNode.getNext();}fixCompleNode fixCompleNode.getNext().getNext();}return resultHead;}public static void printListNode(ListNode pHead){ListNode printNode pHead;while (printNode.getNext() ! null){System.out.print(value: printNode.getValue());System.out.print(, );System.out.print(before: (printNode.getBefore() ! null ? printNode.getBefore().getValue() : ));System.out.print(, );System.out.print(next: (printNode.getNext() ! null ? printNode.getNext().getValue() : ));printNode printNode.getNext();System.out.println();}}public static void main(String[] args) {ListNode oldListNode buildComplexListNode();System.out.println(oldListNode:);printListNode(oldListNode);System.out.println(newListNode:);ListNode mewListNode complexListNode(oldListNode);printListNode(mewListNode);ListNode newListNode_2 complexListNode_2(oldListNode);System.out.println(newListNode_2:);printListNode(newListNode_2);}以上代码中其他未定义方法都沿用 数据结构与算法–链表实现以及应用 中对应的方法。
上一篇数据结构与算法-- 二叉树中和为某一值的路径 下一篇数据结构与算法–二叉查找树转顺序排列双向链表
