Рекурсивная сортировка выбора для связанного списка путем замены ссылок на узлы вместо обмена значениями-C ++ - PullRequest
Новая
       51

Рекурсивная сортировка выбора для связанного списка путем замены ссылок на узлы вместо обмена значениями-C ++

0 голосов
/ 05 января 2020

Я пытаюсь рекурсивно написать сортировку выбора для односвязного списка, и возникают проблемы, когда я хочу поменять местами два узла. Вот моя функция подкачки: 

void swapNode(ListNode** head_ref, ListNode* min, ListNode* prevMin, ListNode* head){
  *head_ref = min;

  ListNode* temp = min->next;
  min->next = head->next;
  head->next = temp;

  prevMin->next = head;

}

И затем она перешла в бесконечное l oop. Когда я изменил последнюю строку "prevMin-> next = head;" во вторую строку вот так: 

void swapNode(ListNode** head_ref, ListNode* min, ListNode* prevMin, ListNode* head){
  *head_ref = min;
  prevMin->next = head;

  ListNode* temp = min->next;
  min->next = head->next;
  head->next = temp;

}

Все отлично работает. Кто-нибудь может увидеть причину здесь?

Вот моя функция сортировки выбора, внутри которой вызывается swapNode: 

ListNode* selectionSortLL(ListNode* head){
  if(head == NULL || head->next == NULL) return head;
  ListNode* cur = head;
  ListNode* min = head, *prevMin = NULL;
  while(cur->next){
    if(cur->next->val < min->val){
      min = cur->next;
      prevMin = cur;
    }
    cur = cur->next;
  }

  if(min != head){
    swapNode(&head, min, prevMin, head);
  }

  head->next = selectionSortLL(head->next);
  return head;
}
...