1#include <stdio.h>
  2#include <stdlib.h>
  3
  4// 单链表节点定义
  5struct SinglyNode {
  6    int data;
  7    struct SinglyNode* next;
  8};
  9
 10// 创建新单链表节点
 11struct SinglyNode* createSinglyNode(int data) {
 12    struct SinglyNode* newNode = (struct SinglyNode*)malloc(sizeof(struct SinglyNode));
 13    newNode->data = data;
 14    newNode->next = NULL;
 15    return newNode;
 16}
 17
 18// 在单链表头部插入节点
 19void insertAtHeadSingly(struct SinglyNode** head, int data) {
 20    struct SinglyNode* newNode = createSinglyNode(data);
 21    newNode->next = *head;
 22    *head = newNode;
 23}
 24
 25// 在单链表尾部插入节点
 26void insertAtTailSingly(struct SinglyNode** head, int data) {
 27    struct SinglyNode* newNode = createSinglyNode(data);
 28    if (*head == NULL) {
 29        *head = newNode;
 30        return;
 31    }
 32
 33    struct SinglyNode* temp = *head;
 34    while (temp->next != NULL) {
 35        temp = temp->next;
 36    }
 37    temp->next = newNode;
 38}
 39
 40// 在单链表的指定位置插入节点
 41void insertAtPositionSingly(struct SinglyNode** head, int data, int position) {
 42    if (position == 1) {
 43        insertAtHeadSingly(head, data);
 44        return;
 45    }
 46
 47    struct SinglyNode* newNode = createSinglyNode(data);
 48    struct SinglyNode* temp = *head;
 49
 50    for (int i = 1; i < position - 1 && temp != NULL; i++) {
 51        temp = temp->next;
 52    }
 53
 54    if (temp == NULL) {
 55        printf("位置超出链表长度\n");
 56        return;
 57    }
 58
 59    newNode->next = temp->next;
 60    temp->next = newNode;
 61}
 62
 63// 删除单链表头部节点
 64void deleteHeadSingly(struct SinglyNode** head) {
 65    if (*head == NULL) return;
 66
 67    struct SinglyNode* temp = *head;
 68    *head = (*head)->next;
 69    free(temp);
 70}
 71
 72// 删除单链表尾部节点
 73void deleteTailSingly(struct SinglyNode** head) {
 74    if (*head == NULL) return;
 75
 76    if ((*head)->next == NULL) {
 77        free(*head);
 78        *head = NULL;
 79        return;
 80    }
 81
 82    struct SinglyNode* temp = *head;
 83    while (temp->next->next != NULL) {
 84        temp = temp->next;
 85    }
 86
 87    free(temp->next);
 88    temp->next = NULL;
 89}
 90
 91// 删除单链表的指定位置节点
 92void deleteAtPositionSingly(struct SinglyNode** head, int position) {
 93    if (*head == NULL) return;
 94
 95    if (position == 1) {
 96        deleteHeadSingly(head);
 97        return;
 98    }
 99
100    struct SinglyNode* temp = *head;
101    for (int i = 1; i < position - 1 && temp->next != NULL; i++) {
102        temp = temp->next;
103    }
104
105    if (temp->next == NULL) {
106        printf("位置超出链表长度\n");
107        return;
108    }
109
110    struct SinglyNode* nodeToDelete = temp->next;
111    temp->next = temp->next->next;
112    free(nodeToDelete);
113}
114
115// 打印单链表
116void printSinglyList(struct SinglyNode* head) {
117    struct SinglyNode* current = head;
118    while (current != NULL) {
119        printf("%d -> ", current->data);
120        current = current->next;
121    }
122    printf("NULL\n");
123}

  1// 双链表节点定义
  2struct DoublyNode {
  3    int data;
  4    struct DoublyNode* next;
  5    struct DoublyNode* prev;
  6};
  7
  8// 创建新双链表节点
  9struct DoublyNode* createDoublyNode(int data) {
 10    struct DoublyNode* newNode = (struct DoublyNode*)malloc(sizeof(struct DoublyNode));
 11    newNode->data = data;
 12    newNode->next = NULL;
 13    newNode->prev = NULL;
 14    return newNode;
 15}
 16
 17// 在双链表头部插入节点
 18void insertAtHeadDoubly(struct DoublyNode** head, int data) {
 19    struct DoublyNode* newNode = createDoublyNode(data);
 20    newNode->next = *head;
 21    if (*head != NULL) {
 22        (*head)->prev = newNode;
 23    }
 24    *head = newNode;
 25}
 26
 27// 在双链表尾部插入节点
 28void insertAtTailDoubly(struct DoublyNode** head, int data) {
 29    struct DoublyNode* newNode = createDoublyNode(data);
 30    if (*head == NULL) {
 31        *head = newNode;
 32        return;
 33    }
 34
 35    struct DoublyNode* temp = *head;
 36    while (temp->next != NULL) {
 37        temp = temp->next;
 38    }
 39    temp->next = newNode;
 40    newNode->prev = temp;
 41}
 42
 43// 在双链表的指定位置插入节点
 44void insertAtPositionDoubly(struct DoublyNode** head, int data, int position) {
 45    if (position == 1) {
 46        insertAtHeadDoubly(head, data);
 47        return;
 48    }
 49
 50    struct DoublyNode* newNode = createDoublyNode(data);
 51    struct DoublyNode* temp = *head;
 52
 53    for (int i = 1; i < position - 1 && temp != NULL; i++) {
 54        temp = temp->next;
 55    }
 56
 57    if (temp == NULL) {
 58        printf("位置超出链表长度\n");
 59        return;
 60    }
 61
 62    newNode->next = temp->next;
 63    if (temp->next != NULL) {
 64        temp->next->prev = newNode;
 65    }
 66    newNode->prev = temp;
 67    temp->next = newNode;
 68}
 69
 70// 删除双链表头部节点
 71void deleteHeadDoubly(struct DoublyNode** head) {
 72    if (*head == NULL) return;
 73
 74    struct DoublyNode* temp = *head;
 75    *head = (*head)->next;
 76
 77    if (*head != NULL) {
 78        (*head)->prev = NULL;
 79    }
 80
 81    free(temp);
 82}
 83
 84// 删除双链表尾部节点
 85void deleteTailDoubly(struct DoublyNode** head) {
 86    if (*head == NULL) return;
 87
 88    if ((*head)->next == NULL) {
 89        free(*head);
 90        *head = NULL;
 91        return;
 92    }
 93
 94    struct DoublyNode* temp = *head;
 95    while (temp->next != NULL) {
 96        temp = temp->next;
 97    }
 98
 99    temp->prev->next = NULL;
100    free(temp);
101}
102
103// 删除双链表的指定位置节点
104void deleteAtPositionDoubly(struct DoublyNode** head, int position) {
105    if (*head == NULL) return;
106
107    if (position == 1) {
108        deleteHeadDoubly(head);
109        return;
110    }
111
112    struct DoublyNode* temp = *head;
113    for (int i = 1; i < position && temp != NULL; i++) {
114        temp = temp->next;
115    }
116
117    if (temp == NULL) {
118        printf("位置超出链表长度\n");
119        return;
120    }
121
122    if (temp->next != NULL) {
123        temp->next->prev = temp->prev;
124    }
125    if (temp->prev != NULL) {
126        temp->prev->next = temp->next;
127    }
128
129    free(temp);
130}
131
132// 打印双链表
133void printDoublyList(struct DoublyNode* head) {
134    struct DoublyNode* current = head;
135    while (current != NULL) {
136        printf("%d <-> ", current->data);
137        current = current->next;
138    }
139    printf("NULL\n");
140}

  1// 循环链表节点定义（与单链表相同）
  2struct CircularNode {
  3    int data;
  4    struct CircularNode* next;
  5};
  6
  7// 创建新循环链表节点
  8struct CircularNode* createCircularNode(int data) {
  9    struct CircularNode* newNode = (struct CircularNode*)malloc(sizeof(struct CircularNode));
 10    newNode->data = data;
 11    newNode->next = newNode; // 初始化时指向自己
 12    return newNode;
 13}
 14
 15// 在循环链表头部插入节点
 16void insertAtHeadCircular(struct CircularNode** head, int data) {
 17    struct CircularNode* newNode = createCircularNode(data);
 18    if (*head == NULL) {
 19        *head = newNode;
 20    } else {
 21        struct CircularNode* temp = *head;
 22        while (temp->next != *head) {
 23            temp = temp->next;
 24        }
 25        temp->next = newNode;
 26        newNode->next = *head;
 27        *head = newNode;
 28    }
 29}
 30
 31// 在循环链表尾部插入节点
 32void insertAtTailCircular(struct CircularNode** head, int data) {
 33    struct CircularNode* newNode = createCircularNode(data);
 34    if (*head == NULL) {
 35        *head = newNode;
 36        return;
 37    }
 38
 39    struct CircularNode* temp = *head;
 40    while (temp->next != *head) {
 41        temp = temp->next;
 42    }
 43    temp->next = newNode;
 44    newNode->next = *head;
 45}
 46
 47// 在循环链表的指定位置插入节点
 48void insertAtPositionCircular(struct CircularNode** head, int data, int position) {
 49    if (position == 1) {
 50        insertAtHeadCircular(head, data);
 51        return;
 52    }
 53
 54    struct CircularNode* newNode = createCircularNode(data);
 55    struct CircularNode* temp = *head;
 56
 57    for (int i = 1; i < position - 1 && temp->next != *head; i++) {
 58        temp = temp->next;
 59    }
 60
 61    if (temp->next == *head) {
 62        printf("位置超出链表长度\n");
 63        return;
 64    }
 65
 66    newNode->next = temp->next;
 67    temp->next = newNode;
 68}
 69
 70// 删除循环链表头部节点
 71void deleteHeadCircular(struct CircularNode** head) {
 72    if (*head == NULL) return;
 73
 74    struct CircularNode* temp = *head;
 75    struct CircularNode* last = *head;
 76
 77    while (last->next != *head) {
 78        last = last->next;
 79    }
 80
 81    if (*head == last) {
 82        free(*head);
 83        *head = NULL;
 84    } else {
 85        last->next = (*head)->next;
 86        *head = (*head)->next;
 87        free(temp);
 88    }
 89}
 90
 91// 删除循环链表尾部节点
 92void deleteTailCircular(struct CircularNode** head) {
 93    if (*head == NULL) return;
 94
 95    struct CircularNode* temp = *head;
 96    struct CircularNode* prev = NULL;
 97
 98    while (temp->next != *head) {
 99        prev = temp;
100        temp = temp->next;
101    }
102
103    if (temp == *head) {
104        free(*head);
105        *head = NULL;
106    } else {
107        prev->next = *head;
108        free(temp);
109    }
110}
111
112// 删除循环链表的指定位置节点
113void deleteAtPositionCircular(struct CircularNode** head, int position) {
114    if (*head == NULL) return;
115
116    if (position == 1) {
117        deleteHeadCircular(head);
118        return;
119    }
120
121    struct CircularNode* temp = *head;
122    struct CircularNode* prev = NULL;
123
124    for (int i = 1; i < position && temp->next != *head; i++) {
125        prev = temp;
126        temp = temp->next;
127    }
128
129    if (temp->next == *head) {
130        printf("位置超出链表长度\n");
131        return;
132    }
133
134    prev->next = temp->next;
135    free(temp);
136}
137
138// 打印循环链表
139void printCircularList(struct CircularNode* head) {
140    if (head == NULL) return;
141    struct CircularNode* current = head;
142    do {
143        printf("%d -> ", current->data);
144        current = current->next;
145    } while (current != head);
146    printf("(head)\n");
147}

  1// 循环双链表节点定义
  2struct CircularDoublyNode {
  3    int data;
  4    struct CircularDoublyNode* next;
  5    struct CircularDoublyNode* prev;
  6};
  7
  8// 创建新循环双链表节点
  9struct CircularDoublyNode* createCircularDoublyNode(int data) {
 10    struct CircularDoublyNode* newNode = (struct CircularDoublyNode*)malloc(sizeof(struct CircularDoublyNode));
 11    newNode->data = data;
 12    newNode->next = newNode;
 13    newNode->prev = newNode;
 14    return newNode;
 15}
 16
 17// 在循环双链表头部插入节点
 18void insertAtHeadCircularDoubly(struct CircularDoublyNode** head, int data) {
 19    struct CircularDoublyNode* newNode = createCircularDoublyNode(data);
 20    if (*head == NULL) {
 21        *head = newNode;
 22    } else {
 23        struct CircularDoublyNode* last = (*head)->prev;
 24        newNode->next = *head;
 25        newNode->prev = last;
 26        last->next = newNode;
 27        (*head)->prev = newNode;
 28        *head = newNode;
 29    }
 30}
 31
 32// 在循环双链表尾部插入节点
 33void insertAtTailCircularDoubly(struct CircularDoublyNode** head, int data) {
 34    struct CircularDoublyNode* newNode = createCircularDoublyNode(data);
 35    if (*head == NULL) {
 36        *head = newNode;
 37        return;
 38    }
 39
 40    struct CircularDoublyNode* last = (*head)->prev;
 41    newNode->next = *head;
 42    newNode->prev = last;
 43    last->next = newNode;
 44    (*head)->prev = newNode;
 45}
 46
 47// 在循环双链表的指定位置插入节点
 48void insertAtPositionCircularDoubly(struct CircularDoublyNode** head, int data, int position) {
 49    if (position == 1) {
 50        insertAtHeadCircularDoubly(head, data);
 51        return;
 52    }
 53
 54    struct CircularDoublyNode* newNode = createCircularDoublyNode(data);
 55    struct CircularDoublyNode* temp = *head;
 56
 57    for (int i = 1; i < position - 1 && temp->next != *head; i++) {
 58        temp = temp->next;
 59    }
 60
 61    if (temp->next == *head) {
 62        printf("位置超出链表长度\n");
 63        return;
 64    }
 65
 66    newNode->next = temp->next;
 67    newNode->prev = temp;
 68    temp->next->prev = newNode;
 69    temp->next = newNode;
 70}
 71
 72// 删除循环双链表头部节点
 73void deleteHeadCircularDoubly(struct CircularDoublyNode** head) {
 74    if (*head == NULL) return;
 75
 76    struct CircularDoublyNode* temp = *head;
 77    struct CircularDoublyNode* last = (*head)->prev;
 78
 79    if (*head == (*head)->next) {
 80        free(*head);
 81        *head = NULL;
 82    } else {
 83        last->next = (*head)->next;
 84        (*head)->next->prev = last;
 85        *head = (*head)->next;
 86        free(temp);
 87    }
 88}
 89
 90// 删除循环双链表尾部节点
 91void deleteTailCircularDoubly(struct CircularDoublyNode** head) {
 92    if (*head == NULL) return;
 93
 94    struct CircularDoublyNode* last = (*head)->prev;
 95    struct CircularDoublyNode* secondLast = last->prev;
 96
 97    if (last == *head) {
 98        free(*head);
 99        *head = NULL;
100    } else {
101        secondLast->next = *head;
102        (*head)->prev = secondLast;
103        free(last);
104    }
105}
106
107// 删除循环双链表的指定位置节点
108void deleteAtPositionCircularDoubly(struct CircularDoublyNode** head, int position) {
109    if (*head == NULL) return;
110
111    if (position == 1) {
112        deleteHeadCircularDoubly(head);
113        return;
114    }
115
116    struct CircularDoublyNode* temp = *head;
117    for (int i = 1; i < position && temp->next != *head; i++) {
118        temp = temp->next;
119    }
120
121    if (temp->next == *head) {
122        printf("位置超出链表长度\n");
123        return;
124    }
125
126    temp->prev->next = temp->next;
127    temp->next->prev = temp->prev;
128    free(temp);
129}
130
131// 打印循环双链表
132void printCircularDoublyList(struct CircularDoublyNode* head) {
133    if (head == NULL) return;
134    struct CircularDoublyNode* current = head;
135    do {
136        printf("%d <-> ", current->data);
137        current = current->next;
138    } while (current != head);
139    printf("(head)\n");
140}