计算机专业面试常见数据结构基础——链表操作详解

一、链表概述

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据域和指针域。链表中的节点可以动态创建和删除，这使得链表在处理动态数据时非常灵活。与数组相比，链表的优点在于插入和删除操作不需要移动其他元素，时间复杂度为O(1)。但链表的缺点是存储空间较大，每个节点都需要额外的空间来存储指针。

二、链表类型

1. 单链表：每个节点只有一个指针域，指向下一个节点。

2. 双链表：每个节点有两个指针域，一个指向下一个节点，另一个指向上一个节点。

3. 循环链表：链表的一个节点的指针域指向链表的第一个节点，形成一个环形。

三、链表操作

1. 创建链表

c

struct ListNode* createList() {

struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));

if (!head) {

return NULL;

}

head->next = NULL;

return head;

}

2. 向链表尾部插入节点

c

void insertTail(struct ListNode* head, int val) {

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

if (!newNode) {

return;

}

newNode->val = val;

newNode->next = NULL;

struct ListNode* temp = head;

while (temp->next) {

temp = temp->next;

}

temp->next = newNode;

}

3. 向链表头部插入节点

c

void insertHead(struct ListNode* head, int val) {

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));

if (!newNode) {

return;

}

newNode->val = val;

newNode->next = head->next;

head->next = newNode;

}

4. 删除链表中的节点

c

void deleteNode(struct ListNode* head, int val) {

struct ListNode* temp = head;

while (temp->next && temp->next->val != val) {

temp = temp->next;

}

if (temp->next) {

struct ListNode* toDelete = temp->next;

temp->next = toDelete->next;

free(toDelete);

}

}

5. 查找链表中的节点

c

struct ListNode* findNode(struct ListNode* head, int val) {

struct ListNode* temp = head;

while (temp && temp->val != val) {

temp = temp->next;

}

return temp;

}

6. 链表反转

c

struct ListNode* reverseList(struct ListNode* head) {

struct ListNode* prev = NULL;

struct ListNode* curr = head;

struct ListNode* next = NULL;

while (curr) {

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

return prev;

}

7. 合并两个有序链表

c

struct ListNode* mergeList(struct ListNode* l1, struct ListNode* l2) {

struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));

dummy->next = NULL;

struct ListNode* prev = dummy;

while (l1 && l2) {

if (l1->val < l2->val) {

prev->next = l1;

l1 = l1->next;

} else {

prev->next = l2;

l2 = l2->next;

}

prev = prev->next;

}

prev->next = l1 ? l1 : l2;

struct ListNode* head = dummy->next;

free(dummy);

return head;

}

四、

链表是一种重要的数据结构，在计算机科学和实际应用中都有广泛的应用。本文介绍了链表的基本概念、类型、操作，以及在实际应用中的常见操作。希望对面试中的数据结构基础有所帮助。