LinkList 操作

Question

LinkList 操作
本題須使用以下 Link List struct 實作
typedef struct node_s{
int data;
struct node_s *next;
} node_t;
針對空的 List，先進行 N個資料節點加入，再進行加入、刪除、交換、反轉等操作。輸出操作後 LinkList 資料。測試資料不會出現相同整數資料。

輸入說明
Line 1, 輸入 N，代表 N 個整數資料節點。
Line 2, 輸入 N 個整數，依序加入節點。
Line 3, 輸入整數 C，代表操作指令的數量。
Line 4~C+3, 輸入操作指令所須整數資料 x或 x, y。操作指令：

1. 從最後面加入資料 x。
2. 刪除最前面節點，若 List 無節點，則不必刪除。
3. 刪除最後面節點，若 List 已無節點，則不必刪除。
4. 刪除 List 內資料為 x 的節點；若 x 不存在則不刪除任何節點。
5. 搜尋 List 內資料為 x 的節點，並在其後加入數值 y 的新節點。若 x 不在 List 中，則不必加入 y 。
6. 反轉 Link List。
7. 交換數值為 x和 y 節點的位置，若 x 或 y 不在 List中，則不必交換。
   輸出說明
   從最前面節點開始依序輸出各節點的值，每個數字中間以空白間隔； 若 List 為空，則輸出"None"

Sample Input 1:最後面加入節點
1
1
3
2
1 2
1 3
Sample Output 1:
2 3

Sample Input 2: 刪除最前面節點
1
3
2
2
2
Sample Output 2:
None

Sample Input 3: 刪除最後面節點
3
1 2 3
4
3
3
3
3
Sample Output 3:
None

Sample Input 4:刪除資料為 x的節點
5
1 2 3 4 5
4
4 1
4 5
4 3
4 6
Sample Output 4:
2 4

Sample Input 5:搜尋並插入新節點
5
1 2 3 4 5
4
5 1 7
5 5 8
5 3 9
5 6 10
Sample Output 5:
1 7 2 3 9 4 5 8

Sample Input 6: 反轉 Link List
5
1 2 3 4 5
3
6
6
6
Sample Output 6:
5 4 3 2 1

Sample Input 7: 交換節點
8
1 2 3 4 5 6 7 8
4
7 1 2
7 7 8
7 1 8
7 2 7
Sample Output 7:
7 8 3 4 5 6 1 2

Answer 1

供参考：

#include <stdio.h>
#include <stdlib.h>
typedef struct node_s {
    int data;
    struct node_s* next;
} node_t;
void create_List(node_t** L,int n)// N個資料節點加入
{
    int i;
    node_t* pt = NULL, * pL = NULL;
    (*L) = (node_t*)malloc(sizeof(node_t));
    (*L)->next = NULL;
    pL = (*L);
    for (i = 0; i < n; i++) {
        pt = (node_t*)malloc(sizeof(node_t));
        pt->next = NULL;
        scanf("%d", &pt->data);
        pL->next = pt;
        pL = pt;
    }
}
void insert_end(node_t* L, int x)//從最後面加入資料 x
{
    node_t* pL = L, * pt = NULL;
    while (pL->next)  pL = pL->next;
    pt = (node_t*)malloc(sizeof(node_t));
    pt->next = NULL;
    pt->data = x;
    pL->next = pt;
}
void delete_first(node_t* L)//刪除最前面節點，若 List 無節點，則不必刪除
{
    node_t* pL = NULL;
    if (!L->next)  return;
    pL = L->next;
    L->next = pL->next;
    free(pL);
}
void delete_end(node_t* L)//刪除最後面節點，若 List 已無節點，則不必刪除
{
    node_t* pL = L, * pre = NULL;
    if (!L->next)  return;
    while (pL->next) { pre = pL; pL = pL->next; }
    pre->next = pL->next;
    free(pL);
}
void deletd_x(node_t* L, int x)//刪除 List 內資料為 x 的節點；
{                               //若 x 不存在則不刪除任何節點
    if (!L->next)  return;
    node_t* pL = L->next, * pre = L;
    while (pL) {
        if (pL->data == x) {
            pre->next = pL->next;
            free(pL);
            pL = pre;
        }
        else {
            pre = pL;
            pL = pL->next;
        }
    }
}
void search_x_insert_y(node_t* L, int  x, int  y)//搜尋 List 內資料為 x 的節點，並在其後加入
{                                              //數值 y 的新節點。若 x 不在 List 中，則不必加入y
    if (!L->next)  return;
    node_t* pL = L->next, * pt = NULL;
    while (pL && pL->data != x) pL = pL->next;
    if (pL != NULL) {
        pt = (node_t*)malloc(sizeof(node_t));
        pt->next = NULL;
        pt->data = y;
        pt->next = pL->next;
        pL->next = pt;
    }
}
void convert_List(node_t* L) //反轉 Link List
{
    if (!L->next)  return;
    node_t* pL = L->next, * pt = NULL;
    L->next = NULL;
    while (pL) {
        pt = pL;
        pL = pL->next;
        pt->next = L->next;
        L->next = pt;
    }
}
void swap_x_y(node_t* L, int x, int y)//交換數值為 x和 y 節點的位置，
                                       //若 x 或 y 不在 List中，則不必交換
{
    if (!L->next)  return;
    node_t* pL = L->next, * prL = L, 
          * px = NULL, * py = NULL,
          * prx = NULL, *pry = NULL;
    while (pL) {
        if (pL->data == x) {
            prx = prL;
            px = pL;
        }
        else if (pL->data == y) {
            pry = prL;
            py = pL;
        }
        if (px && py)  break;
        prL = pL;
        pL = pL->next;
    }
    if (px && py) {
        if (pry == px) {
            prx->next = px->next;
            px->next = py->next;
            py->next = px;
        }
        else {
            prL = py->next;
            py->next = px->next;
            px->next = prL;
            prx->next = py;
            pry->next = px;
        }
    }
}
void print_List(node_t* L)//從最前面節點開始依序輸出各節點的值，每個數字
{                          //以中間空白間隔,若 List 為空，則輸出"None" 
    node_t* pL = L;
    if (L == NULL || L->next == NULL)
        printf("None");
    else {
        while (pL->next) {
            printf(pL->next == L->next ? "%d" : " %d", pL->next->data);
            pL = pL->next;
        }
        //printf("\n");
    }
}
int main()
{
    int N, C, s, x, y;
    node_t* List = NULL;
    scanf("%d", &N);
    create_List(&List, N);
    scanf("%d", &C);
    while (C--) {
        scanf("%d", &s);
        switch (s)
        {
        case 1:scanf("%d", &x); insert_end(List, x); break;
        case 2:delete_first(List); break;
        case 3:delete_end(List); break;
        case 4:scanf("%d", &x); deletd_x(List, x); break;
        case 5:scanf("%d%d", &x, &y); search_x_insert_y(List, x, y); break;
        case 6:convert_List(List); break;
        case 7:scanf("%d%d", &x, &y); swap_x_y(List, x, y); break;
        default:
            break;
        }
    }
    print_List(List);
    return 0;
}