복잡 한 링크 복사

복잡 한 링크 (각 노드 에 노드 값 과 두 개의 지침 이 있 고 하 나 는 다음 노드 를 가리 키 며 다른 특수 지침 은 임의의 노드 를 가리 키 는 것) 를 입력 하고 결 과 를 복사 한 복잡 한 링크 의 head 로 되 돌려 줍 니 다.(출력 결과 에서 인자 의 노드 인용 을 되 돌려 주지 마 십시오. 그렇지 않 으 면 문제 풀이 프로그램 이 비어 있 습 니 다)
이 문제 의 사고 1: 처음부터 원래 의 링크 를 옮 겨 다 니 고 처음으로 링크 만 저장 하 는 전후 관 계 를 옮 겨 다 니 며 그의 random 노드 관 계 를 저장 하지 않 습 니 다.두 번 째 로 다시 옮 겨 다 니 며 그의 random 노드 를 저장 합 니 다. 이런 시간 복잡 도 는 n 제곱 입 니 다.
사고 2: 한 노드 를 옮 겨 다 닐 때마다 노드 정 보 를 hash 로 저장 합 니 다. 이렇게 첫 번 째 로 옮 겨 다 닌 후에 노드 의 전후 관 계 를 형성 하고 hash 를 이용 하여 노드 의 random 관 계 를 얻 으 며 공간 을 이용 하여 시간 을 바 꿉 니 다.
사고방식 3: (1) a - b - c - d 를 a - a '- b - b' - c '- d - d' 로 바 꾸 기;(2) 링크 를 옮 겨 다 니 며 복 제 된 노드 의 random 을 복사 합 니 다.(3) 노드 를 나 누 어 두 개의 링크 를 형성한다.
종합 적 으로 분석 하면 코드 는 다음 과 같다.

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        //      ，     
        if(pHead == null)
            return null;

        //     
        RandomListNode currentNode = pHead; 
        while(currentNode != null){
            RandomListNode temp = new RandomListNode(currentNode.label);
            temp.next = currentNode.next;
            currentNode.next = temp;
            currentNode = temp.next;
        }

        // random     
        currentNode = pHead;
        while(currentNode != null){
            if(currentNode.random != null){
                currentNode.next.random = currentNode.random.next;
            }
            currentNode = currentNode.next.next;
        }

        //       
        RandomListNode newList = pHead.next;
        RandomListNode oldList = pHead;
        currentNode = pHead.next;
        while(currentNode !=null)
        {
            oldList.next = oldList.next.next;
            if(currentNode.next != null){
                currentNode.next = currentNode.next.next;
            }

            oldList = oldList.next;
            currentNode = currentNode.next;

        }
        return newList;
    }
}