연결된 목록의 특정 정렬

Question

예를 들어 연결된 목록이 3 : 1 -> 4-> 1-> 7-> 5-> 7 등의 특정 방법으로 연결된 목록을 정렬해야합니다. 이렇게 : 7-> 1-> 7-> 1-> 3-> 4-> 5. 그래서 내가 이해하는 목록에서 예를 들어 max 요소를 찾아 처음에 추가하고 현재 목록에서 그런 요소를 삭제해야한다면, 목록의 중간에있는 요소의 예를 들어 처음으로 바꾸는 방법이 있는지 궁금합니다. 목록. 아니면 이러한 요소를 삭제하고 주어진 데이터로 메모리를 할당하고 처음에 추가해야합니까? 전반적으로 프로그래밍 클래스 테스트의 작업이며 단일 연결 목록을 사용하여 수행해야합니다.

Answer 1

여기에 하나의 접근 방식 :

1. 이 목록 Q을 만듭니다 분류되지 않은 목록 P 주어진다.
2. 추가 max(P)-Q.
3. max(P)을 P에서 삭제하십시오.
4. 추가 min(P)-Q.
5. P에서 min(P)을 제거하십시오.
6. 2 ~ 5 단계를 한 번 더 반복하십시오.
7. P을 오름차순으로 정렬하십시오.
8. 추가 P to Q.

Q 지금 당신의 는 목록을 분류.

이 방법은 Pnext 포인터의 길이가 더 당신이 목록의 노드 포인터에 대한 포인터가있는 경우는 head 포인터 즉, 단독으로 링크 된 목록에 노드를 교체 할 수 있습니다 4.

Answer 2

미만 노드 없다 '가정 . 어쨌든 목록을 최대한으로 찾아야하기 때문에 그렇게 할 수 있습니다. (그렇지 않으면이 함수 subseqnet 호출 alwas 전면에 같은 7을 가져올 것, 마지막으로 최대를 선택주의하십시오.)

void max_to_front(struct node **head) 
{ 
    struct node **mp = head; // current max pointer address 
    struct node **pv = head; // iterator pointer address 
    struct node *nd = *head; // iterator pointer 
    int mx; 

    // nothing to do for empty or single-node lists 
    if (*head == NULL || (*head)->next == NULL) return; 

    // find maximum 
    mx = nd->value; 
    while (nd) { 
     if (nd->value >= mx) { 
      mp = pv; 
      mx = nd->value; 
     } 
     pv = &nd->next; 
     nd = nd->next; 
    } 

    // move max to the front, i.e. update the pointers 
    nd = *mp; 
    *mp = (*mp)->next; 
    nd->next = *head; 
    *head = nd; 
} 

항상 당신이 온 어떤을 통해 노드 포인터의 주소를 포함하는 방법 pv 주 현재 노드 nd이므로 업데이트 할 수 있습니다. mp은 최대 값을 갖는 노드의 포인터 주소 일뿐입니다.