[algorithm] 인터뷰 질문 : 새 노드를 만들지 않고 정렬 된 두 개의 단일 연결 목록 병합

Program / 글쓴이

이것은 면접을위한 필기 시험 중에 묻는 프로그래밍 질문입니다. “이미 정렬 된 두 개의 단일 연결 목록이 있습니다.이를 병합하고 새 추가 노드를 생성하지 않고 새 목록의 헤드를 반환해야합니다. 반환 된 목록도 정렬되어야합니다.”

메소드 서명은 다음과 같습니다. Node MergeLists (Node list1, Node list2);

노드 클래스는 다음과 같습니다.

class Node{
    int data;
    Node next;
}

나는 많은 솔루션을 시도했지만 여분의 노드 나사를 만들지 않았습니다. 도와주세요.

다음은 블로그 항목 http://techieme.in/merging-two-sorted-singly-linked-list/입니다.

답변

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

답변

새 노드 할당을 피하기 위해 재귀가 필요하지 않습니다.

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  }
  list1.next = list2;
  return head;
}

답변

Node MergeLists(Node node1, Node node2)
{
   if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;

   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
      node1 = node1.next;
   else
   {
      head = node2;
      node2 = node2.next;
   }

   Node current = head;
   while((node1 != null) ||( node2 != null))
   {
      if (node1 == null) {
         current.next = node2;
         return head;
      }
      else if (node2 == null) {
         current.next = node1;
         return head;
      }

      if (node1.data < node2.data)
      {
          current.next = node1;
          current = current.next;

          node1 = node1.next;
      }
      else
      {
          current.next = node2;
          current = current.next;

          node2 = node2.next;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}

답변

정렬 된 두 개의 연결 목록 A와 B를 병합하는 방법에 대한 알고리즘은 다음과 같습니다.

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

여기서 C는 출력 목록입니다.

답변

엄마, 재귀 없음!

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

답변

반복은 아래와 같이 할 수 있습니다. 복잡성 = O (n)

public static LLNode mergeSortedListIteration(LLNode nodeA, LLNode nodeB) {
    LLNode mergedNode ;
    LLNode tempNode ;

    if (nodeA == null) {
        return nodeB;
      }
      if (nodeB == null) {
        return nodeA;
      }


    if ( nodeA.getData() < nodeB.getData())
    {
        mergedNode = nodeA;
        nodeA = nodeA.getNext();
    }
    else
    {
        mergedNode = nodeB;
        nodeB = nodeB.getNext();
    }

    tempNode = mergedNode;

    while (nodeA != null && nodeB != null)
    {

        if ( nodeA.getData() < nodeB.getData())
        {
            mergedNode.setNext(nodeA);
            nodeA = nodeA.getNext();
        }
        else
        {
            mergedNode.setNext(nodeB);
            nodeB = nodeB.getNext();
        }
        mergedNode = mergedNode.getNext();
    }

    if (nodeA != null)
    {
        mergedNode.setNext(nodeA);
    }

    if (nodeB != null)
    {
        mergedNode.setNext(nodeB);
    }
    return tempNode;
}

답변

Node mergeList(Node h1, Node h2) {
    if (h1 == null) return h2;
    if (h2 == null) return h1;
    Node head;
    if (h1.data < h2.data) {
        head = h1;
    } else {
        head = h2;
        h2 = h1;
        h1 = head;
    }

    while (h1.next != null && h2 != null) {
        if (h1.next.data < h2.data) {
            h1 = h1.next;
        } else {
            Node afterh2 = h2.next;
            Node afterh1 = h1.next;
            h1.next = h2;
            h2.next = afterh1;

            if (h2.next != null) {
                h2 = afterh2;
            }
        }
    }
    return head;
}