美文网首页
面试题35(剑指offer)--复杂链表的复制

面试题35(剑指offer)--复杂链表的复制

作者: Tiramisu_b630 | 来源:发表于2019-08-17 15:58 被阅读0次

    题目:

    请实现函数ComplexListNode Clone(ComplexListNode head),复制一个复杂链表。在复杂链表中,每个结点除了有一个Next指针指向下一个结点外,还有一个Sibling指向链表中的任意结点或者NULL。

    思路:

    1. 在每个节点后插入要复制的节点
    2. 复制节点间的连接关系
    3. 拆解成两个链表

    代码:

        static class ListNode{
            int val;
            ListNode next;
            ListNode sibling;
            ListNode(int val){
                this.val=val;
            }
        }   
        private static ListNode copyList(ListNode a) {
            copy(a);//第一步
            copySecondLink(a);//第二步
            return copySep(a);//第三步
        }
    
        private static ListNode copySep(ListNode node) {
            ListNode head=node;
            ListNode newHead=null;
            ListNode newNode=null;
            if (head!=null){
                newHead=newNode=head.next;
                head.next=newNode.next;
                head=head.next;
            }
            while (head!=null){
                newNode.next=head.next;
                newNode=newNode.next;
                head.next=newNode.next;
                head=head.next;
            }
            return newHead;
        }
    
        private static void copySecondLink(ListNode node) {
            ListNode a=node;
            while (a!=null){
                if (a.sibling!=null){
                    a.next.sibling=a.sibling.next;
                }
                a=a.next.next;
            }
        }
    
        private static void copy(ListNode node) {
            ListNode a=node;
            while (a!=null){
                ListNode tmp=a.next;
                ListNode newNode=new ListNode(a.val);
                newNode.next=tmp;
                a.next=newNode;
                a=tmp;
            }
        }
    

    相关文章

      网友评论

          本文标题:面试题35(剑指offer)--复杂链表的复制

          本文链接:https://www.haomeiwen.com/subject/fxkksctx.html