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。操作指令：
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
供参考：
#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;
}