단일 연결 목록을 포인터로 정렬

Question

나는 포인터 만 조작하거나 키를 사용하지 않고 단일 정렬 목록을 버블 정렬을 사용하여 정렬하려고합니다.

다음은 for 루프와 루프에서 무한정 달라 붙습니다. 나는 이것이 왜 있는지 이해하지 못한다. 아무도 왜 목록의 끝 부분을 찾을 수 없는지 내게 설명 할 수 있습니까? 키 (데이터) 교환되도록 내가 코드를 변경하는 경우

Node* sort_list(Node* head) 
{ 
    Node * temp; 
    Node * curr; 
    for(bool didSwap = true; didSwap;) { 
      didSwap = false; 
      for(curr = head; curr->next != NULL; curr = curr->next) { 
        if(curr->key > curr->next->key) { 
          temp = curr; 
          curr = curr->next; 
          curr->next = temp; 
          didSwap = true; 
        } 
        cout << curr->next->key << endl; 
      } 
    } 
    return head; 

}

는 다음 기능이 제대로 작동하지만 어떤 이유로 나는 단지 포인터를 조작하여 작동 할 수 없습니다입니다. ptr1->ptr2->ptr3 :

이 세 회원 목록을 보자 :

Answer 1

논리 오류, 당신은 다음 코드를 사용하여 무한 루프를 만드는 -

temp = curr; 
curr = curr->next; 
curr->next = temp; 

내가, 전자 next_of_current가 현재 가리키는 때문에 curr-> 다음은 항상 CURR되며 NULL 수 없습니다 결코;

다음 목록은 한 방향으로 이동할 수 있기 때문에 목록을 수정하기 위해 이전 포인터를 사용해야합니다. 그래서, Think - A-> B-> C-> NULL 인 경우; C와 B를 바꾸면 새로운 목록은 여전히 ​​A -> B를 가리키고 다음 반복은 잘못 될 것입니다 ... 이전에 다음을 수정하지 않으므로.

그래서, 또 다른 구현 될 수있다 -이 도움이

Node* sort_list(Node* head) { 
    Node * curr; 
    Node * prev; 
    for(bool didSwap = true; didSwap;) { 
     didSwap = false; 
     prev = head; 
     for(curr = head; curr->next != NULL; curr = curr->next) { 
       if(curr->key > curr->next->key) { 
         if (head == curr) { 
          head = curr->next;  
          curr->next = head->next; 
          head->next = curr; 
          prev = head; 
         } else { 
          prev->next = curr->next; 
          curr->next = prev->next->next; 
          prev->next->next = curr 
         } 
         didSwap = true; 
       } else if (head != curr) { 
        prev = prev->next; 
       } 
       //cout << curr->next->key << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element) 
      } 
    } 
    return head; 
} 

희망, 감사합니다.

Answer 2

당신은 다음과 같은 문제가 있습니다. 교환하기 전에 포인터를 다음과 같이 설정하십시오 : curr=ptr1; curr->next=ptr2; curr->next->next=ptr3. 스왑을 수행하면 curr=ptr2; curr->next=ptr1; curr->next->next=ptr2이 수신됩니다.

예. 당신은 ptr3을 잃었습니다. 당신은 다음과 같이 내부 루프의 코드를 변경해야 : 당신이 교환 할

temp = curr; 
temp->next = curr->next->next; // Save ptr3 
curr = curr->next; 
curr->next = temp; 
didSwap = true; 

Answer 3

필드가 value입니다. 그러나 node을 바꾸면 next 필드가 변경되며 질문이 조금 복잡해 지므로 next 필드를 올바르게 유지해야합니다. 한마디로, value 변경은 간단하고 좋은 방법입니다.

Answer 4

node *sorted_list(node *head) { 
    node *index1,*index2; 
    for(index1=head;index1->next!=NULL;index1=index1->next) { 
     for(index2=index1->next;index2!=NULL;index2=index2->next) { 
      if(index1->data>index2->data) { 
       int temp=index1->data; 
       index1->data=index2->data; 
       index2->data=temp; 
      } 
     } 
    } 
    return head; 
}