PTA: 6 - 6 링크 연결 (20 점)

빅 뱅 반기 데이터 구조
데이터 구조 제목 집합
링크 조인 트
이 문 제 는 두 개의 질서 있 는 링크 를 합 친 간단 한 함 수 를 실현 해 야 한다.링크 노드 정 의 는 다음 과 같 습 니 다.

struct ListNode {
    int data;
    struct ListNode *next;
};

함수 인터페이스 정의:

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);

그 중에서 list 1 과 list 2 는 사용자 가 들 어 온 두 개의 data 오름차 순 으로 연 결 된 링크 의 헤드 포인터 입 니 다.함수 mergelists 는 두 개의 링크 를 data 오름차 순 으로 연 결 된 링크 로 합 쳐 결과 링크 의 헤드 포인터 로 되 돌려 줍 니 다.심판 테스트 프로그램 샘플:

#include 
#include 

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); /*    ，    */
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("
");
}

int main()
{
    struct ListNode  *list1, *list2;

    list1 = createlist();
    list2 = createlist();
    list1 = mergelists(list1, list2);
    printlist(list1);
	
    return 0;
}

/*            */

입력 예시:

1 3 5 7 -1
2 4 6 -1

출력 예시:

1 2 3 4 5 6 7 

문제 풀이:

struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    int len = 0;
    int a[10000];
    struct ListNode *p1 = list1;
    struct ListNode *p2 = list2;
    struct ListNode *head = NULL;
    struct ListNode *tail = NULL;
    struct ListNode *q;
    while(p1)
    {
        a[len] = p1->data;
        p1 = p1->next;
        len++;
    }
    while(p2)
    {
        a[len] = p2->data;
        p2 = p2->next;
        len++;
    }
    int i, j, temp;
    for(i=1; ia[j+1])
            {
                temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
            }
        }
    }
 
     for(i = 0; i < len; i++)
      {
          q = (struct ListNode  *)malloc(sizeof(struct ListNode));
          q->data = a[i];
           if(head == NULL)
         {
             head = q;
             head->next = NULL;
         }
           if(tail != NULL)//tail     
            {
              tail->next = q;
         }
             tail = q;
             tail->next = NULL;
      }
      return head;
}

거품 정렬:

 “3 2 4 1”           
   （    ）
3 2 4 1（  ）
2 3 4 1（  3 2，  ）
2 3 4 1（  3 4，   ）
2 3 1 4（  1 4 ，  ）
     ，         ，               3       
   （    ）
2 3 1 4（       ）
2 3 1 4（  2 3，   ）
2 1 3 4（  3 1，  ）
     ，          
   （    ）
2 1 3 4（       ）
1 2 3 4（  2 1，  ）
  ，      。

선택 방법 정렬:

            ：
1.     n  （ a[0]~a[n-1])      ，   a[0]  ：
2.       n-1  （a[1]~a[n-1])      ，   a[1]
  ：
···········
 n-1 ：          (a[n-2]~a[n-1]）      ， 
  a[n-2]  ：
~~~    ：~~~/* n      */
for(k=0;k