c++ 链表 虚拟头节点

虚拟头节点是一种特殊的链表节点，它不存储任何元素值，只用来作为链表的起始节点。在C++中可以通过定义一个指向虚拟头节点的指针来表示整个链表。中，我们可以看到定义了一个名为`firstHead`的虚拟头节点，它的值为0。该虚拟头节点的`next`指针指向真正的头节点`head`。通过这种方式，我们可以方便地对链表进行操作，无需单独处理头节点的特殊情况。

例如，在示例中的`swapPairs`函数中，通过移动指针的方式来交换链表中相邻两个节点的位置。在操作过程中，使用了虚拟头节点来简化操作，使得代码更加清晰易懂。

总之，虚拟头节点是一种常用的技巧，用于简化链表操作的处理逻辑，特别是在处理头节点时。它只是一个指针，不存储任何实际的数据，但在代码中起到了重要的作用。

相关问题

头插法反转链表c++

头插法是一种反转链表的方法，它通过将当前节点插入到已经反转的部分链表的头部来实现反转。具体步骤如下：

1. 创建一个虚拟头节点dummy，并将其next指针指向原链表的头节点head。
2. 创建一个pre指针，初始时指向虚拟头节点dummy。
3. 使用循环遍历到达需要反转的区间的前一个节点pre。
4. 创建一个指针p，初始时指向pre的下一个节点。
5. 使用循环将p节点插入到pre节点之后，并更新p节点的next指针和pre节点的next指针。
6. 循环完成后，返回dummy节点的next指针，即为反转后的链表头节点。

以下是可以参考的C++代码示例：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        
        for (int i = 1; i < left; i++) {
            pre = pre->next;
        }
        
        ListNode* p = pre->next;
        ListNode* tmp;
        
        for (int i = left; i < right; i++) {
            tmp = p->next;
            p->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        
        return dummy->next;
    }
};

蓝桥杯两两交换链表c++完整代码

下面是蓝桥杯两两交换链表c的完整代码：

#include <iostream>

using namespace std;

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

ListNode* swapPairs(ListNode* head) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *curr = dummy;

    while (curr->next != nullptr && curr->next->next != nullptr) {
        ListNode *first = curr->next;
        ListNode *second = curr->next->next;

        first->next = second->next;
        second->next = first;
        curr->next = second;

        curr = curr->next->next;
    }

    return dummy->next;
}

void printList(ListNode *head) {
    ListNode *curr = head;
    while (curr != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}

int main() {
    ListNode *head = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);
    head->next = node2;
    node2->next = node3;
    node3->next = node4;

    cout << "原链表：";
    printList(head);

    ListNode *newHead = swapPairs(head);

    cout << "交换后的链表：";
    printList(newHead);

    return 0;
}

代码中的`swapPairs`函数用于实现两两交换链表中的节点。它从虚拟头节点dummy开始，每次交换两个节点，并将当前节点curr指向两个交换后的节点中的第二个节点。

`printList`函数用于打印链表中的元素。

在主函数中，创建了一个链表，并将其交给`swapPairs`函数进行两两交换。最后，使用`printList`函数打印交换后的链表。