数据结构中的链表：概念、操作与实战
第一部分 链表分类及常见形式
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的。
1. 单链表
最基本的链表形式，每个节点包含数据和指向下一个节点的指针。
// 单链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;
2. 双链表
每个节点包含指向前一个节点和后一个节点的指针，可以双向遍历。
// 双链表节点结构
typedef struct DNode {int data;struct DNode* prev;struct DNode* next;
} DNode;
3. 循环链表
尾节点指向头节点形成环状结构，可以是单向或双向循环。
// 循环单链表示例
Node* createCircularList(int data) {Node* head = (Node*)malloc(sizeof(Node));head->data = data;head->next = head; // 指向自己形成循环return head;
}
4. 带头节点的链表
有一个不存储实际数据的头节点，简化操作。
// 带头节点的单链表
Node* createListWithHead() {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;return head;
}
第二部分 链表常见操作
1. 创建节点
// 创建单链表节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if(newNode == NULL) {printf("内存分配失败\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}
2. 插入节点
// 在单链表头部插入
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*head = newNode;
}// 在单链表尾部插入
void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if(*head == NULL) {*head = newNode;return;}Node* current = *head;while(current->next != NULL) {current = current->next;}current->next = newNode;
}// 在双链表特定位置插入
void insertDNodeAfter(DNode* prevNode, int data) {if(prevNode == NULL) return;DNode* newNode = (DNode*)malloc(sizeof(DNode));newNode->data = data;newNode->next = prevNode->next;newNode->prev = prevNode;if(prevNode->next != NULL) {prevNode->next->prev = newNode;}prevNode->next = newNode;
}
3. 删除节点
// 删除单链表中指定值的节点
void deleteNode(Node** head, int key) {Node *temp = *head, *prev = NULL;if(temp != NULL && temp->data == key) {*head = temp->next;free(temp);return;}while(temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}if(temp == NULL) return;prev->next = temp->next;free(temp);
}// 删除双链表中的节点
void deleteDNode(DNode** head, DNode* delNode) {if(*head == NULL || delNode == NULL) return;if(*head == delNode) *head = delNode->next;if(delNode->next != NULL) delNode->next->prev = delNode->prev;if(delNode->prev != NULL) delNode->prev->next = delNode->next;free(delNode);
}
4. 遍历链表
// 遍历单链表
void printList(Node* head) {Node* current = head;while(current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}// 反向遍历双链表
void printListReverse(DNode* tail) {DNode* current = tail;while(current != NULL) {printf("%d -> ", current->data);current = current->prev;}printf("NULL\n");
}
5. 查找节点
// 在单链表中查找
Node* search(Node* head, int key) {Node* current = head;while(current != NULL) {if(current->data == key) {return current;}current = current->next;}return NULL;
}
6. 反转链表
// 反转单链表
void reverseList(Node** head) {Node* prev = NULL;Node* current = *head;Node* next = NULL;while(current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}*head = prev;
}
第三部分 链表编程题例子
1. 检测链表是否有环
int hasCycle(Node *head) {if(head == NULL || head->next == NULL) return 0;Node *slow = head, *fast = head->next;while(slow != fast) {if(fast == NULL || fast->next == NULL) return 0;slow = slow->next;fast = fast->next->next;}return 1;
}
2. 合并两个有序链表
Node* mergeTwoLists(Node* l1, Node* l2) {Node dummy;Node* tail = &dummy;dummy.next = NULL;while(l1 != NULL && l2 != NULL) {if(l1->data <= l2->data) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = (l1 != NULL) ? l1 : l2;return dummy.next;
}
3. 删除链表的倒数第N个节点
Node* removeNthFromEnd(Node* head, int n) {Node dummy;dummy.next = head;Node *fast = &dummy, *slow = &dummy;for(int i = 0; i <= n; i++) {fast = fast->next;}while(fast != NULL) {fast = fast->next;slow = slow->next;}Node* toDelete = slow->next;slow->next = slow->next->next;free(toDelete);return dummy.next;
}
4. 链表的中间节点
Node* middleNode(Node* head) {Node *slow = head, *fast = head;while(fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;
}
5. 回文链表判断
int isPalindrome(Node* head) {if(head == NULL || head->next == NULL) return 1;// 找到中间节点Node *slow = head, *fast = head;while(fast->next != NULL && fast->next->next != NULL) {slow = slow->next;fast = fast->next->next;}// 反转后半部分Node *prev = NULL, *curr = slow->next, *next;while(curr != NULL) {next = curr->next;curr->next = prev;prev = curr;curr = next;}slow->next = prev;// 比较前后两部分Node *p1 = head, *p2 = slow->next;while(p2 != NULL) {if(p1->data != p2->data) return 0;p1 = p1->next;p2 = p2->next;}return 1;
}
6. 两个链表的交点
Node *getIntersectionNode(Node *headA, Node *headB) {if(headA == NULL || headB == NULL) return NULL;Node *a = headA, *b = headB;while(a != b) {a = (a == NULL) ? headB : a->next;b = (b == NULL) ? headA : b->next;}return a;
}
链表是一种非常灵活的数据结构，在内存分配、插入删除操作等方面比数组更有优势。掌握链表的各种操作和算法是程序员的基本功，对于理解更复杂的数据结构如树、图等也有很大帮助。通过不断练习这些题目，可以深入理解链表的特性和应用场景。