数据结构与算法--复杂链表的复制

「爱情、让人受尽委屈。」 2023-01-22 06:00 21阅读 0赞

#### 复杂链表的复制 ####

*  题目：实现一个函数complexListNode 复制一个复杂链表。在链表中，每个节点除了有一个next指针指向下一个节点，还有另外一个before节点，before节点指向链表中任意一个节点，或者null节点。
 *  链表节点定义使用之前文章 [数据结构与算法–链表实现以及应用][Link 1] 中链表节点的定义，以及链表中其他方法实现都沿用以上文章中有详细的说明。
 *  如下节点定义：

public class ListNode implements Comparable<ListNode> { 
        private Integer value;
        private ListNode next;
        private ListNode before;
    ......
    }

*  如下图中包含的5个阶段的复杂链表，图中实线箭头表示next指针，虚线表示before指针，简单画出如下，我们省略了null指针没有画出来：  
    ![在这里插入图片描述][20210518160605456.png]
 *  分析：
    
     *  方法一：如上链表的结构看最简单的方式先遍历一次，将节点复制，并且用next 链接节点，得到基础结构
     *  在循环查找每一个节点的before节点，因为此处before节点是随机指向，可能指向本节点之前的节点，因此每次都需要遍历一次链表来查找对应的节点信息
     *  时间复杂度O(N2)
     *  方法二：为了避免before节点查找的复杂性，先遍历一次oldList，复制next指针，并且将oldNode，newNode存储到map中，
     *  第二次遍历，此时我们已经知道了oldNode~ newNode的对应关系，我们在查找到oldList的before指向的时候，直接从map中获取到对应newNode，这样通过O（1） 时间获取到before的值
     *  此处空间换时间的方法
     *  方法三：换一种思路，能否不用辅助空间情况下来实现O(n)的时间复杂度，
     *  第一次遍历，直接将访问到的节点复制新节点，并且插入到访问到的节点后面，如下图：  
        ![在这里插入图片描述][20210518161757213.png]
     *  第二次遍历，设置新建节点的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指针，并且将oldNode，newNode存储到map中， * 第二次遍历同时遍历oldList，newList，直接通过oldList的before指向的oldListNode从mep中获取newNode， * O(1)时间获取到before值 * */
        public static ListNode complexListNode(ListNode pHead){ 
            if(pHead == null || pHead.getNext() == null){ 
                return pHead;
            }
            Map<ListNode, 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);
        }

*  以上代码中其他未定义方法都沿用 [数据结构与算法–链表实现以及应用][Link 1] 中对应的方法。

[上一篇：数据结构与算法-- 二叉树中和为某一值的路径][--]  
[下一篇：数据结构与算法–二叉查找树转顺序排列双向链表][Link 2]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114397878
[20210518160605456.png]: /images/20221020/d7451e9cdbb64034a0692e068ae7c294.png
[20210518161757213.png]: /images/20221020/c7352324c789424e942cdf1b098d6f6e.png
[--]: https://blog.csdn.net/liaojiamin0102/article/details/116923539
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/117084229