C++中的链表：单链表、双向链表、循环链表。(结构体版本)

链表是一种常见的数据结构，它由多个节点（结构体）组成，每个节点包含一个数据域和一个指针域，指针域指向下一个节点（在双向链表中，还会有一个指针域指向上一个节点）。链表的一个重要特点是可以动态地添加或删除节点，因此常用于需要频繁插入或删除元素的场合。

C++中的链表是一种常用的数据结构，用于存储和组织数据。链表是由一系列节点组成的，每个节点包含一个数据元素和一个指向下一个节点的指针。C++中常用的链表包括单链表、双向链表和循环链表。

1. 单链表（Singly Linked List）：单链表是最简单的链表形式，每个节点只有一个指向下一个节点的指针。单链表的优点是插入和删除节点的时间复杂度都为O(1)，但是查找节点的时间复杂度为O(n)。

2. 双向链表（Doubly Linked List）：双向链表每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。双向链表的优点是查找节点的时间复杂度为O(n/2)，删除和插入节点的时间复杂度仍为O(1)，但是它需要更多的空间存储指向前一个节点的指针。

3. 循环链表（Circular Linked List）：循环链表和单链表类似，只不过最后一个节点的指针不是NULL，而是指向链表的头节点。循环链表的优点是可以像双向链表一样从后往前遍历链表，但是它也需要更多的空间存储最后一个节点的指针。

下面是C++中链表的常用操作：

1. 创建一个节点：可以定义一个结构体来表示链表的节点，包括数据元素和指向下一个节点的指针。

2. 插入节点：插入节点时，需要把插入节点的指针指向它的下一个节点，而前一个节点的指针指向插入节点。

3. 删除节点：删除节点时，需要将前一个节点的指针指向要删除节点的下一个节点，然后再释放要删除的节点的空间。

4. 遍历节点：从链表的头节点开始遍历每个节点，直到最后一个节点。可以使用while循环和指针来遍历链表。

5. 查找节点：遍历链表中的每个节点，直到找到所需的节点。可以使用while循环和指针来查找节点。

6. 反转链表：可以使用三个指针来反转链表中的节点，分别指向当前节点、前一个节点和下一个节点，依次修改节点的指针方向。

7. 合并链表：可以创建一个新的链表，遍历两个链表的所有节点，按照大小顺序依次插入到新的链表中。

以上是链表的基本操作，可以根据具体情况进行扩展和优化。

1. 获取链表长度：可以使用一个计数器和一个指针来遍历链表，每经过一个节点计数器加1，最终得到链表的长度。

2. 判断链表是否为空：检查链表的头节点是否为NULL即可。

3. 获取链表中间节点：可以使用快慢指针的方法，快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针正好在链表的中间。

4. 检测链表是否有环：可以使用快慢指针的方法，快指针每次走两步，慢指针每次走一步，如果存在环，那么快指针一定会追上慢指针。

5. 删除链表中重复的节点：可以使用一个hash表来记录每个数据元素是否出现过，如果出现过则删除节点。

6. 求链表的交点：如果两个链表有交点，那么它们从交点开始的所有节点都是相同的，可以先分别求出两个链表的长度，然后让较长的链表先走一段距离，直到和较短的链表一样长，然后一起遍历两个链表，找到第一个相同的节点即为交点。

7. 分割链表：可以创建两个新的链表，遍历原链表中的每个节点，根据某个条件将节点插入到其中一个链表或者另一个链表中。

8. 链表排序：可以使用快速排序、归并排序等算法来对链表进行排序，需要注意链表的特殊结构，如节点的指针方向等。

以上是C++中链表的一些常用操作，链表作为一种重要的数据结构，在实际开发中经常被使用，需要掌握其基本原理和常用操作。

C++中实现链表可以使用指针，指向链表的头节点或尾节点，然后通过指针操作链表。下面分别介绍单链表、双向链表和循环链表的实现。

单链表

单链表是一种最基本的链表形式，它的每个节点只包含一个指向下一个节点的指针。单链表的特点是占用的内存比较小，但是查找节点的效率较低。

下面是单链表的一个简单实现：

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node* next;
};

class LinkedList {
public:
    LinkedList() {
        head = nullptr;
        size = 0;
    }

    void add(int value) {
        Node* newNode = new Node{ value, nullptr };
        if (head == nullptr) {
            head = newNode;
        }
        else {
            Node* node = head;
            while (node->next != nullptr) {
                node = node->next;
            }
            node->next = newNode;
        }
        size++;
    }

    void remove(int index) {
        if (index >= size) {
            cout << "Invalid index" << endl;
            return;
        }
        if (index == 0) {
            Node* nodeToRemove = head;
            head = head->next;
            delete nodeToRemove;
        }
        else {
            Node* node = head;
            for (int i = 0; i < index - 1; i++) {
                node = node->next;
            }
            Node* nodeToRemove = node->next;
            node->next = nodeToRemove->next;
            delete nodeToRemove;
        }
        size--;
    }

    int get(int index) {
        if (index >= size) {
            cout << "Invalid index" << endl;
            return -1;
        }
        Node* node = head;
        for (int i = 0; i < index; i++) {
            node = node->next;
        }
        return node->data;
    }

    int getSize() {
        return size;
    }

private:
    Node* head;
    int size;
};

int main() {
    LinkedList list;

    list.add(1);
    list.add(2);
    list.add(3);

    cout << list.get(0) << endl; // 输出 1
    cout << list.get(1) << endl; // 输出 2
    cout << list.get(2) << endl; // 输出 3

    list.remove(1); // 删除第 2 个节点

    cout << list.get(0) << endl; // 输出 1
    cout << list.get(1) << endl; // 输出 3

    return 0;
}

///////////////////////////////////////////////////////////////////////////

链表是一种常用的数据结构，C++中常见的链表有单链表、双向链表、循环链表等。下面分别对这三种链表进行讲解并演示代码。

1. 单链表

单链表是最基本的链表形式，每个节点只包含一个指针，指向下一个节点。单链表的优点是插入和删除节点方便，缺点是无法快速访问链表中的某个节点。

单链表的节点定义如下：

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

其中，val表示节点的值，next是一个指向下一个节点的指针。

以下是单链表的常见操作：

• 创建单链表：

ListNode* createLinkedList(vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return dummy->next;
}

其中，使用dummy节点作为头节点，方便后续操作。

• 遍历单链表：

void traverseLinkedList(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        // do something with cur->val
        cur = cur->next;
    }
}

插入节点：

void insertNode(ListNode* node, int val) {
    ListNode* new_node = new ListNode(val);
    new_node->next = node->next;
    node->next = new_node;
}

其中，将新节点插入到指定节点后面。

• 删除节点：

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

其中，将指定节点的值修改为下一个节点的值，并将指针指向下一个节点的下一个节点。

1. 双向链表

双向链表在单链表的基础上，每个节点多了一个指向前一个节点的指针。双向链表的优点是可以快速访问链表中的任意节点，缺点是插入和删除节点相对麻烦。

双向链表的节点定义如下：

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

其中，prev表示指向前一个节点的指针，next表示指向下一个节点的指针。

以下是双向链表的常见操作：

• 创建双向链表：

ListNode* createDoublyLinkedList(vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur->next->prev = cur;
        cur = cur->next;
    }
    return dummy->next

遍历双向链表：

void traverseDoublyLinkedList(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        // do something with cur->val
        cur = cur->next;
    }
}

插入节点：

void insertNode(ListNode* node, int val) {
    ListNode* new_node = new ListNode(val);
    new_node->prev = node;
    new_node->next = node->next;
    node->next->prev = new_node;
    node->next = new_node;
}

其中，将新节点插入到指定节点后面。

• 删除节点：

void deleteNode(ListNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node;
}

其中，将指定节点的前一个节点的指针指向后一个节点，后一个节点的指针指向前一个节点。

1. 循环链表

循环链表和单链表类似，不同之处在于最后一个节点的指针指向第一个节点，形成一个环。循环链表的优点是可以遍历链表无限次，缺点是插入和删除节点相对麻烦。

循环链表的节点定义如下

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

其中，next指向下一个节点，最后一个节点的next指向第一个节点。

以下是循环链表的常见操作：

• 创建循环链表：

ListNode* createCircularLinkedList(vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    cur->next = dummy->next;
    return dummy->next;
}

其中，使用dummy节点作为头节点，最后一个节点的next指向头节点，形成一个环。

• 遍历循环链表：

void traverseCircularLinkedList(ListNode* head) {
    ListNode* cur = head;
    do {
        // do something with cur->val
        cur = cur->next;
    } while (cur != head);
}

其中，使用do-while循环，确保至少遍历一次链表。

• 插入节点：

void insertNode(ListNode* node, int val) {
    ListNode* new_node = new ListNode(val);
    new_node->next = node->next;
    node->next = new_node;
    swap(node->val, new_node->val);
}

其中，将新节点插入到指定节点后面，并将指定节点的值与新节点的值交换，保证指定节点的值为新节点的值。

• 删除节点：

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

其中，将指定节点的值修改为下一个节点的值，并将指针指向下一个节点的下一个节点。

以上就是链表的基本操作，可以根据实际需要进行修改和拓展。

下面是一个完整的C++实现示例，包括单链表、双向链表和循环链表的定义和操作：

#include <iostream>
#include <vector>

using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Definition for doubly-linked list.
struct DoublyListNode {
    int val;
    DoublyListNode* prev;
    DoublyListNode* next;
    DoublyListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

// Definition for circular linked list.
struct CircularListNode {
    int val;
    CircularListNode* next;
    CircularListNode(int x) : val(x), next(NULL) {}
};

// Create a singly-linked list
ListNode* createLinkedList(vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return dummy->next;
}

// Traverse a singly-linked list
void traverseLinkedList(ListNode* head) {
    ListNode* cur = head;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

// Insert a node into a singly-linked list
void insertNode(ListNode* node, int val) {
    ListNode* new_node = new ListNode(val);
    new_node->next = node->next;
    node->next = new_node;
    swap(node->val, new_node->val);
}

// Delete a node from a singly-linked list
void deleteNode(ListNode* node) {
    node->val = node->next->val;
    ListNode* tmp = node->next;
    node->next = tmp->next;
    delete tmp;
}

// Create a doubly-linked list
DoublyListNode* createDoublyLinkedList(vector<int>& nums) {
    DoublyListNode* dummy = new DoublyListNode(-1);
    DoublyListNode* cur = dummy;
    for (int i = 0; i < nums.size(); i++) {
        cur->next = new DoublyListNode(nums[i]);
        cur->next->prev = cur;
        cur = cur->next;
    }
    return dummy->next;
}

// Traverse a doubly-linked list
void traverseDoublyLinkedList(DoublyListNode* head) {
    DoublyListNode* cur = head;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

// Insert a node into a doubly-linked list
void insertNode(DoublyListNode* node, int val) {
    DoublyListNode* new_node = new DoublyListNode(val);
    new_node->prev = node;
    new_node->next = node->next;
    node->next->prev = new_node;
    node->next = new_node;
}

// Delete a node from a doubly-linked list
void deleteNode(DoublyListNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node;
}

// Create a circular linked list
CircularListNode* createCircularLinkedList(vector<int>& nums) {
    CircularListNode* dummy = new CircularListNode(-1);
    CircularListNode* cur = dummy;
    for (int i =0; i < nums.size(); i++) {
cur->next = new CircularListNode(nums[i]);
cur = cur->next;
}
cur->next = dummy->next;
return dummy->next;
}
// Traverse a circular linked list
void traverseCircularLinkedList(CircularListNode* head) {
CircularListNode* cur = head;
do {
cout << cur->val << " ";
cur = cur->next;
} while (cur != head);
cout << endl;
}
// Insert a node into a circular linked list
void insertNode(CircularListNode* node, int val) {
CircularListNode* new_node = new CircularListNode(val);
new_node->next = node->next;
node->next = new_node;
swap(node->val, new_node->val);
}
// Delete a node from a circular linked list
void deleteNode(CircularListNode* node) {
node->val = node->next->val;
CircularListNode* tmp = node->next;
node->next = tmp->next;
delete tmp;
}
int main() {
// Test singly-linked list
vector<int> nums = {1, 2, 3, 4, 5};
ListNode* head = createLinkedList(nums);
traverseLinkedList(head);
insertNode(head->next->next, 6);
traverseLinkedList(head);
deleteNode(head->next->next);
traverseLinkedList(head);
// Test doubly-linked list
vector<int> nums2 = {1, 2, 3, 4, 5};
DoublyListNode* head2 = createDoublyLinkedList(nums2);
traverseDoublyLinkedList(head2);
insertNode(head2->next->next, 6);
traverseDoublyLinkedList(head2);
deleteNode(head2->next->next);
traverseDoublyLinkedList(head2);

// Test circular linked list
vector<int> nums3 = {1, 2, 3, 4, 5};
CircularListNode* head3 = createCircularLinkedList(nums3);
traverseCircularLinkedList(head3);
insertNode(head3->next->next, 6);
traverseCircularLinkedList(head3);
deleteNode(head3->next->next);
traverseCircularLinkedList(head3);

return 0;

这段代码中，我们分别定义了三种不同类型的链表，然后实现了它们的常用操作，包括创建链表、遍历链表、插入节点和删除节点等。在测试时，我们分别创建了一个单链表、一个双向链表和一个循环链表，然后对它们进行了一系列操作，并输出了操作后的链表内容。

需要注意的是，在单链表和循环链表中，删除节点时需要先用当前节点的后继节点的值覆盖当前节点的值，然后再删除后继节点。这样可以避免无法访问到前驱节点的问题。而在双向链表中，由于每个节点都有前驱节点，因此删除节点时可以直接修改前驱节点和后继节点的指针即可。

此外，在插入节点时，需要先创建一个新节点，并将其插入到目标节点的后面。在单链表和循环链表中，这可以通过修改目标节点和新节点的指针实现

；在双向链表中，还需要修改新节点的前驱节点的指针。

最后需要注意的是，这段代码只是一个简单的演示，实际开发中可能需要根据具体需求进行修改和扩展。同时，需要注意链表的操作时间复杂度，例如在单链表和循环链表中插入和删除节点的时间复杂度为 O(1)，而在双向链表中插入和删除节点的时间复杂度为 O(1)。