链表

链表（LinkList）

一种逻辑有序，但存储结构无需有序的数据结构。

带虚拟头节点的链表可以统一一些操作。

// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
ListNode *dummyNode = new ListNode(-1);
dummyNode->next = head;

链表反转

非递归

void reverseLinkedList(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* next = cur->next;
            cur->next= pre;
            pre = cur;
            cur = next;
        }
    }

递归的实现

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

判定环