O (1) 시간에 두 개의 원형 이중 연결된 목록을 함께 병합하는 방법은 무엇입니까?

Question

리스트가 원형 이중화 된 목록으로 저장되는 Fibonacci 힙을 구현하고 있습니다.내가하려는 것은 하나의 링크 된 목록에서 임의의 노드에 대한 포인터가 주어지며 다른 링크 노드는 O (1) 시간에 함께 병합하고 싶습니다.나는 이것을 그리는 것을 시도했지만, 나는 이것을하는 방법을 알아낼 수 없었다.여기 의사의 첫 번째 아이디어가 있습니다.

union(Node one, Node two) {
    if other = nil
        return

    p1 = one
    p2 = one.right
    p3 = two
    p4 = two.right

    p1.right = p4
    p4.left = p1
    p2.right = p3
    p3.left = p2
}

.

각 Node에는 left 및 right 속성이있어 노드를 왼쪽 및 오른쪽에 각각 저장합니다.그러나 이것은 작동하지 않았습니다.누구나 두 개의 연결된 목록을 함께 병합하는 방법을 알아낼 수 있습니까?

Answer 1

임시 변수를 사용할 필요가 없습니다.아래 그림과 연관된 의사 코드를 참조하십시오.회색 포인터를 색깔의 상대방에 재 할당하고자합니다.지시 사항의 순서로 조심해야합니다.

one.right.left = two.left;  //red
two.left.right = one.right; //blue

one.right = two; //green
two.left = one;  //purple

.