[알고리즘 학습] 복잡 한 링크 복사

문제 설명: 복잡 한 링크 를 복사 합 니 다.복잡 한 링크 에서 모든 노드 는 다음 노드 를 가리 키 는 next 지침 을 제외 하고 sibing 지침 은 링크 의 임 의 노드 나 NULL 을 가리킨다.
해법 1: "폭파"
해법 분석: 1. 첫 번 째 배열 을 옮 겨 다 니 며 복제 체인 의 next 와 각 노드 값 을 복사 합 니 다.시간 이 필요 합 니 다 O (n) 2. 두 번 째 로 옮 겨 다 니 며 이중 for 순환 은 원 링크 에 따라 복사 체인 의 slibing 지침 을 연결 합 니 다.소요 시간 O (n ^ 2) 3. 소요 시간 복잡 도 는 O (n ^ 2), 공간 복잡 도 는 O (1)
참조 코드 는 다음 과 같 습 니 다.

/** *         * * @author kesar * */
static class Node
{
    int val;
    Node next;
    Node slibing;

    public Node(){}

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

    @Override
    public String toString()
    {
        return "Node [val=" + val + "]";
    }
}

/** *      ：    。    next ，           slibing   。       ：O(n^2)，      ：O(1) * * @param oHead * @return */
public static Node copy1(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    //          
    Node cHead = new Node(oHead.val);

    // oMove             ，cMove              
    //   Node      next   
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
    {
        cMove.next = new Node(oMove.val);
    }

    //   slibing    
    for (Node oMove = oHead, cMove = cHead; oMove != null; cMove = cMove.next, oMove = oMove.next)
    {
        if (oMove.slibing == null)
            continue;
        //     ：     slibing          copy      
        Node findNode = cHead;
        for (; findNode != null && findNode.val != oMove.slibing.val; findNode = findNode.next)
            ;
        //     ：findNode    
        cMove.slibing = findNode;
    }

    return cHead;
}

해법 2: 보조 공간 사용
해법 분석: 1. HashMap (Key: 원래 링크 의 결산 점, Value: 링크 의 결산 점 복사) 을 사용 합 니 다. 공간 복잡 도 는 O (n) 2 입 니 다. 첫 번 째 배열 을 옮 겨 다 닙 니 다. 복사 체인 의 결산 점 을 만 들 때마다 HashMap 에 결산 점 이 존재 하 는 지, 존재 하지 않 는 지 찾 아서 만 든 다음 에 결산 점 을 HashMap 에 저장 해 야 합 니 다.소요 시간 O (n) 4. 소요 시간 복잡 도 는 O (n), 공간 복잡 도 는 O (n)
참조 코드 는 다음 과 같 습 니 다.

/** *      ：  HashMap O(1)                  for  。 O(n)     O(n)   。     O(n)，     ：O(n) * * @param oHead * @return */
public static Node copy2(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    //     ：Key：       ，Value：        
    HashMap<Node, Node> map = new HashMap<Node, Node>();

    //            
    Node cHead = new Node(oHead.val);
    map.put(oHead, cHead);
    if (oHead.slibing != null)
    {
        cHead.slibing = new Node(oHead.slibing.val);
        map.put(oHead.slibing, cHead.slibing);
    }
    //   ：     ，          。
    //      ：  map           ，     ，     ，          ，  put map ，        
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
    {
        if (map.containsKey(oMove))
        {
            cMove.next = map.get(oMove);
        }
        else
        {
            cMove.next = new Node(oMove.val);
            map.put(oMove, cMove.next);
        }
        Node slibing = oMove.slibing;
        if (slibing == null)
        {
            continue;
        }
        if (map.containsKey(slibing))
        {
            cMove.next.slibing = map.get(slibing);
        }
        else
        {
            cMove.next.slibing = new Node(slibing.val);
            map.put(slibing, cMove.next.slibing);
        }
    }
    return cHead;
}

해법 3: "신장 분열 법"
해법 분석: 1. 원 링크 를 옮 겨 다 닌 다.원 링크 의 모든 노드 뒤에 해당 하 는 복사 노드 를 삽입 하여 원 링크 를 1 배 늘 립 니 다.2. 원 링크 를 옮 겨 다 닌 다.결점 을 복사 한 slibing 연결 하기;3. 원 링크 를 옮 겨 다 닌 다.원점 과 복제 결점 을 '분열' 하여 next 를 연결 합 니 다.4. 시간 이 필요 한 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.
참조 코드 는 다음 과 같 습 니 다.

/** * @param oHead * @return */
public static Node copy3(Node oHead)
{
    if (oHead == null)
    {
        return null;
    }
    // 1."  "
    for (Node oMove = oHead; oMove != null; oMove = oMove.next)
    {
        //     
        Node copy = new Node(oMove.val);
    //              
        copy.next = oMove.next;
        oMove.next = copy;
        //         
        oMove = copy;
    }
    // 2.   slibing
    for (Node oMove = oHead; oMove != null; oMove = oMove.next)
    {
        if (oMove.slibing == null)
        {
            continue;
        }
        Node copy = oMove.next;
        copy.slibing = oMove.slibing.next;
        oMove = copy;
    }
    // 3."  "，       next       next
    Node cHead = oHead.next;
    oHead.next = cHead.next;
    cHead.next = null;
    for (Node oMove = oHead.next, cMove = cHead; oMove != null; oMove = oMove.next, cMove = cMove.next)
    {
        Node copy = oMove.next;
        oMove.next = copy.next;
        copy.next = null;
        cMove.next = copy;
    }
    return cHead;
}

첨부: 원본 주소