正文

链表数据结构详解：轻松掌握算法实现技巧

/0 浏览量
0529

链表是一种常见的基础数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。相比于数组，链表在插入和删除操作上更加灵活，但同时也需要更多的内存空间来存储指针。本文将详细解析链表数据结构，并介绍几种常见的链表算法实现技巧。

链表的基本概念

节点结构

链表中的每个节点包含两部分：数据和指针。数据部分存储实际的数据值，指针部分存储指向下一个节点的地址。

struct ListNode {
    int val;
    struct ListNode *next;
};

链表类型

  • 单向链表：每个节点只有一个指向下一个节点的指针。
  • 双向链表：每个节点包含两个指针，一个指向前一个节点，一个指向下一个节点。
  • 循环链表：最后一个节点的指针指向链表的第一个节点，形成一个循环。

链表操作

创建链表

创建链表需要先定义节点结构，然后动态分配内存，并设置指针。

struct ListNode* createList(int n) {
    struct ListNode *head = NULL, *pre = NULL, *temp = NULL;
    for (int i = 0; i < n; i++) {
        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = i;
        temp->next = NULL;
        if (pre) {
            pre->next = temp;
        } else {
            head = temp;
        }
        pre = temp;
    }
    return head;
}

插入节点

插入节点分为头插法、尾插法和指定位置插入。

// 头插法
void insertHead(struct ListNode *head, int val) {
    struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = head;
    head = temp;
}

// 尾插法
void insertTail(struct ListNode *head, int val) {
    struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    if (head == NULL) {
        head = temp;
    } else {
        struct ListNode *pre = head;
        while (pre->next) {
            pre = pre->next;
        }
        pre->next = temp;
    }
}

// 指定位置插入
void insertPos(struct ListNode *head, int pos, int val) {
    struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    if (pos == 0) {
        temp->next = head;
        head = temp;
    } else {
        struct ListNode *pre = head;
        for (int i = 0; i < pos - 1; i++) {
            if (pre == NULL) {
                return;
            }
            pre = pre->next;
        }
        temp->next = pre->next;
        pre->next = temp;
    }
}

删除节点

删除节点分为删除头节点、删除尾节点和指定位置删除。

// 删除头节点
void deleteHead(struct ListNode *head) {
    if (head == NULL) {
        return;
    }
    struct ListNode *temp = head;
    head = head->next;
    free(temp);
}

// 删除尾节点
void deleteTail(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    struct ListNode *pre = head;
    while (pre->next->next) {
        pre = pre->next;
    }
    free(pre->next);
    pre->next = NULL;
}

// 指定位置删除
void deletePos(struct ListNode *head, int pos) {
    if (head == NULL) {
        return;
    }
    if (pos == 0) {
        deleteHead(head);
    } else {
        struct ListNode *pre = head;
        for (int i = 0; i < pos - 1; i++) {
            if (pre == NULL) {
                return;
            }
            pre = pre->next;
        }
        if (pre->next == NULL) {
            return;
        }
        struct ListNode *temp = pre->next;
        pre->next = temp->next;
        free(temp);
    }
}

遍历链表

遍历链表是链表操作中最基本的操作，可以通过循环遍历每个节点来访问链表中的数据。

void traverseList(struct ListNode *head) {
    struct ListNode *temp = head;
    while (temp) {
        printf("%d ", temp->val);
        temp = temp->next;
    }
    printf("\n");
}

链表算法实现技巧

查找倒数第k个节点

struct ListNode* findKthToTail(struct ListNode *head, int k) {
    struct ListNode *fast = head, *slow = head;
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

合并两个有序链表

struct ListNode* merge(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *cur = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    free(dummy);
    return cur->next;
}

反转链表

struct ListNode* reverseList(struct ListNode *head) {
    struct ListNode *pre = NULL, *cur = head, *next = NULL;
    while (cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

删除链表的中间节点

void deleteNode(struct ListNode *node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

总结

链表是一种重要的数据结构，它在很多算法中都有应用。本文详细介绍了链表的基本概念、操作和常见算法实现技巧。通过学习和掌握链表，可以帮助我们更好地理解和解决各种编程问题。

-- 展开阅读全文 --