정렬 된 이중 연결 목록에 삽입

Question

정렬 된 이중 연결 목록의 머리 노드에 대한 포인터와 목록에 삽입 할 정수가 지정되었습니다. 노드를 만들고 목록의 적절한 위치에 삽입해야한다고 말했습니다 그 정렬 된 순서가 유지됩니다. 헤드 노드가 NULL 일 수 있습니다.

샘플 입력

NULL 데이터 = 2

NULL < -> 4 < - -> 6 -> NULL 데이터 = 5

예제 출력

2 <

NULL < -> NULL

NULL < - 2 < -> 4 < -> 5 < -> 6 -> NULL

위의 문제를 시도했습니다.하지만 시간 초과로 인해 프로그램이 종료되고 있습니다. 아래 코드에서 무엇을 잘못하고 있습니다. Node 클래스와 main 함수가 이미 있다고 가정합니다. 많은 분들께 미리 감사드립니다 !!

Node SortedInsert(Node head,int data) { 

    Node newn = new Node(); 

    newn.data = data; 
    newn.prev=null; 
    newn.next = null; 

    Node ptr = head; 
    Node nex=head.next; 

    while(ptr!=null && nex!=null) { 
     if(ptr.data<=newn.data && nex.data>=newn.data) { 
      newn.next = nex; 
      newn.prev = ptr; 
      nex.prev = newn; 
      ptr.next = newn; 
     }    
     else { 
      nex=nex.next; 
      ptr=ptr.next; 
     } 
    } 

    if(ptr!=null && nex==null) { 
     if(ptr.data>=newn.data) { 
      newn.next=ptr; 
      ptr.prev=newn; 
      newn.prev=null; 
      head=newn; 
     } 
     else { 
      ptr.next=newn; 
      newn.prev = head; 
     } 
    } 

    if(head==null) { 
     head = newn; 
    } 

    return head; 

} 

Answer 1

매우 간단합니다 : 당신은 성공적으로 삽입 한 후 루프의 돌발되지 않습니다. 따라서 노드를 삽입하는 위치를 계속 반복합니다. 약간의 변경을하십시오.

if(ptr.data>=newn.data) 
{ 
    newn.next=ptr; 
    ptr.prev=newn; 
    newn.prev=null; 
    head=newn; 
    break; 
} 

그러나 중복 코드가 작성되었습니다. 이 짧은 중복 코드가 포함되어 있지 않습니다 헤드 노드가 다음/이전 노드를 얻으려고 노력하는 동안 NullPointerException이 게타 것이다 null의 경우

Node SortedInsert(Node head,int data) { 

    Node newn = new Node(); 
    newn.data = data; 

    Node ptr = head; 

    if (ptr == null) { 
     head = newn; 

    } else if (ptr.data > newn.data) { 
     newn.next = ptr; 
     ptr.prev = newn; 
     head = newn; 

    } else { 
     Node nex = head.next; 

     while (nex != null && nex.data <= newn.data) { 
      ptr = nex; 
      nex = nex.next; 
     } 

     ptr.next = newn; 
     newn.prev = ptr; 

     if (nex != null) { 
      nex.prev = newn; 
      newn.next = nex; 
     } 
    } 

    return head; 
} 

Answer 2

합니다. 먼저 다음을 점검해야합니다.

Node sortedInsert(Node head, int data) { 
    Node newn = new Node(); 
    newn.data = data; 
    //Basic case: the list is empty, so the head is null 
    if (head==null) { 
     return newn; 
    } 
    //If node is not null 
    Node aux= head; 
    Node auxPrev; 
    while (aux!=null && aux.data<data) { 
     auxPrev=aux; 
     aux=aux.next; 
    } 
    //auxPrev will be null if we are going to insert in the first position 
    if (auxPrev!=null) 
     auxPrev.next=newn; 
     newn.prev=auxPrev; 
     head=newn; 
    } 
    //aux will be null if we insert in the last position 
    if (aux!=null) { 
     aux.prev=newn; 
     newn.next=aux; 
    } 
    return head; 
}