C++中链表操作实例分析

什么是链表

链表（Linked List）是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分，一个是数据，另一个是指向下一个节点的指针。通过这些指针将节点串联起来，形成一个链表。

链表的数据结构定义

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

链表中每个节点的数据类型为 int，指针类型为 ListNode*，其中 next 指向下一个节点，当 next 为NULL 时表示链表的末尾。

链表的基本操作

链表的常见操作包括以下几个：

1. 创建链表

创建链表需要动态分配内存，创建节点并将各个节点串联起来，常用的方式有头插法和尾插法。

头插法

头插法创建一个链表时，从头结点开始逐个创建节点，并将新创建的节点插入到链表头部。

ListNode* createListByHeadInsert(vector<int> vec) {
    ListNode* head = new ListNode(0);
    for (int i = 0; i < vec.size(); i++) {
        ListNode* node = new ListNode(vec[i]);
        node->next = head->next;
        head->next = node;
    }
    return head->next;
}

尾插法

尾插法创建一个链表时，从头结点开始逐个创建节点，并将新创建的节点插入到链表尾部。

ListNode* createListByTailInsert(vector<int> vec) {
    ListNode* head = new ListNode(0);
    ListNode* tail = head;
    for (int i = 0; i < vec.size(); i++) {
        ListNode* node = new ListNode(vec[i]);
        tail->next = node;
        tail = tail->next;
    }
    return head->next;
}

2. 遍历链表

遍历链表就是依次访问链表中每个节点，可以通过 while 循环和 for 循环来实现。

void traverseList(ListNode* head) {
    while (head) {
        cout << head->val << "->";
        head = head->next;
    }
    cout << "NULL" << endl;
}

3. 插入节点

在链表中插入一个节点，需要先找到插入位置的前一个节点，然后将新节点插入到该节点之后。

void insertListNode(ListNode* pos, ListNode* node) {
    node->next = pos->next;
    pos->next = node;
}

4. 删除节点

在链表中删除一个节点，需要先找到要删除的节点的前一个节点，然后将该节点从链表中剔除。

void deleteListNode(ListNode* head, ListNode* node) {
    while (head && head->next != node) {
        head = head->next;
    }
    if (head && head->next == node) {
        head->next = head->next->next;
    }
}

5. 反转链表

反转链表是指将链表的方向逐一反向，例如原先链表是 1->2->3->4->5，反转后的链表为 5->4->3->2->1。

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

示例说明

以下是基于链表进行归并排序和删除倒数第n个节点的两个示例说明。

1. 归并排序

题目要求：对链表进行归并排序，注意时间复杂度

示例输入：[4,3,2,1]

示例输出：[1,2,3,4]

归并排序的时间复杂度为 O(nlogn)，其中 n 表示链表的长度。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = NULL;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return mergeTwoLists(left, right);
    }
};

2. 删除倒数第n个节点

题目要求：删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例输入：[1,2,3,4,5] n = 2

示例输出：[1,2,3,5]

算法思路：使用双指针，快指针先走 k 步，然后快慢指针一起走，当快指针走到链表末尾时，慢指针所在节点的 next 指针就是要删除节点的前一个节点。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        if (fast == NULL) {
            return head->next;
        }
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

总结

链表是一种常见的数据结构，常用于解决链式存储的问题。在 C++ 中，我们可以通过定义 ListNode 结构体来自定义链表类型，并通过基本操作来方便地对链表进行增删改查操作。同时在实际开发中，我们也可以借助链表来解决一些经典的算法问题。