数据结构-C语言版本（二）链表

数据结构中的链表：概念、操作与实战

第一部分 链表分类及常见形式

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的元素在内存中不是连续存储的。

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;
}

链表是一种非常灵活的数据结构，在内存分配、插入删除操作等方面比数组更有优势。掌握链表的各种操作和算法是程序员的基本功，对于理解更复杂的数据结构如树、图等也有很大帮助。通过不断练习这些题目，可以深入理解链表的特性和应用场景。