자바 복잡 한 링크 복사 실현

복잡 한 링크 를 입력 하 십시오(각 노드 에 노드 값 과 두 개의 지침 이 있 습 니 다.하 나 는 다음 노드 를 가리 키 고 다른 특수 지침 은 임의의 노드 를 가리 키 고 있 습 니 다).결 과 는 복 제 된 복잡 한 링크 의 head 로 되 돌아 갑 니 다.
코드
    static class ListNode {
        int val;
        ListNode next;
        ListNode other;

        public ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + (next == null ? "null" : next.val) +
                    ", other=" + (other == null ? "null" : other.val) +
                    "}";
        }
    }

    /**
     *   
     *     a->b->c
     *     a->a1->b->b1->c->c1
     * @param head
     */
    private static void copy(ListNode head) {
        ListNode listNode = head;
        while (listNode != null) {
            //                
            ListNode copy = new ListNode(listNode.val);
            copy.next = listNode.next;

            //            next  ,     next         next  
            //    a->b,    a->a1->b
            listNode.next = copy;
            //       ,      
            listNode = copy.next;
        }
    }

    /**
     *   other  
     * @param head
     */
    private static void setOther(ListNode head) {
        ListNode listNode = head;
        // listNode      ,copy        ,        
        while (listNode != null) {
            //               
            ListNode copy = listNode.next;

            //      other    null ,     other     other   next  
            // a -> a1 -> b -> b1    a1 a     ,b1 b     
            // |          ↑          a.other b,b.next   b1(         )
            // |_ _ _ _ _ |            a1 other   a.other b next,   a.other.next
            if (listNode.other != null) {
                copy.other = listNode.other.next;
            }
            //                 ,      next  ,      
            listNode = copy.next;
        }
    }

    /**
     *          
     * @param head
     * @return
     */
    private static ListNode disConnect(ListNode head) {
        ListNode listNode = head;
        ListNode copyHead = null;
        ListNode copyNode = null;
        if (listNode != null) {
            //                   next  (      )
            copyHead = listNode.next;
            //         
            copyNode = listNode.next;
            //             next    next(         next)
            listNode.next = copyNode.next;
            //          ,           
            listNode = listNode.next;
        }

        while (listNode != null) {
            //        next       next
            // a -> a1 -> b -> b1,   a1 -> b1
            copyNode.next = listNode.next;
            //          
            copyNode = copyNode.next;

            //           next    next(         next)
            // a -> a1 -> b -> b1,   a -> b
            listNode.next = copyNode.next;
            //          ,          
            listNode = listNode.next;
        }

        return copyHead;
    }

    public static ListNode cloneNode(ListNode head) {
        if (head == null) {
            return null;
        }
        copy(head);
        setOther(head);
        return disConnect(head);
    }

    public static void main(String[] args) {
        ListNode root = bulidList();
        ListNode copy = cloneNode(root);
        while (root != null) {
            System.out.println(root.toString());
            root = root.next;
        }
        while (copy != null) {
            System.out.println(copy.toString());
            copy = copy.next;
        }
    }

    private static ListNode bulidList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        node1.other = node3;
        node4.other = node1;
        return node1;
    }

좋은 웹페이지 즐겨찾기