链表

203. 移除链表元素（Easy）

因为是单链表，所以正常情况下，处理head→val会比较麻烦。要分开讨论。

为次，可以创建一个额外的newHead→head ，从newHead 开始遍历和删除。最后返回newHead→next。

ListNode* removeElements(ListNode* head, int val)
{
    auto* newHead = new ListNode(0, head);

    for (ListNode* p = newHead; p != nullptr; p = p->next)
    {
        while (p->next != nullptr && p->next->val == val)
        {
            ListNode* node = p->next;
            p->next = node->next;
            delete node;
        }
    }

    head = newHead->next;
    delete newHead;
    return head;
}

206. 反转链表（Easy）

双指针

实际上会用到三个指针。

• prev：指向上一个节点。

• cur：指向当前节点。

• tmp：暂存cur下一个节点，因为cur反向后会丢失下一个节点

ListNode* reverseList(ListNode* head)
{
    ListNode *prev = nullptr, *cur = head;

    while (cur)
    {
        ListNode* tmp = cur->next;  // 暂存当前节点
        cur->next = prev;           // 反向
        prev = cur;                 // 更新prev节点到当前节点
        cur= tmp;                   // 更新cur到下一个节点
    }

    return prev;
}

利用 swap()

ListNode* reverseList(ListNode* head)
{
    ListNode *prev = nullptr, *cur = head;

    for (; cur; swap(prev, cur))
        swap(prev, cur->next);

    return prev;
}

92. 反转链表 II（Medium）

保存不被反转的两个部分

ListNode* reverseBetween(ListNode* head, int left, int right)
{
    if (!head->next || left == right) return head;
	
    ListNode *pre = nullptr, *front = head;
    ListNode* cur = head;

    for (int i = 1; i <= right; i++)
    {
        if (i+1 == left) front = cur;		// 保存前部分不反转的最后一个节点
        if (i == right) pre = cur->next;	// 保存后部分不反转的第一个节点

        cur = cur->next;
    }
    // 第一个结点如果也在反转范围，则起始结点就是 head
    cur = left > 1 ? front->next : front;
    for (int i = 0; i < right - left + 1; i++)
    {
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    // 反转最后一个结点指向反转后的第一个节点
    if(left > 1) front->next = pre;

    return head;
}

24. 两两交换链表中的节点（Medium）

不使用虚拟头结点

ListNode* swapPairs(ListNode* head)
{
    if (!head || !head->next) return head;

    ListNode *prev = head, *cur = head->next;
    ListNode *tmp = nullptr;
    head = cur;

    while (cur)
    {
        if (tmp) tmp->next = cur;		// 1

        prev->next = cur->next;			// 2
        cur->next = prev;				// 3
        tmp = prev;
        prev = prev->next;
        cur = prev ? prev->next : nullptr;
    }

    return head;
}

使用虚拟头结点

ListNode* swapPairs(ListNode* head)
{
    // 虚头结点指向head
    auto dummy = new ListNode(head);
    ListNode *prev = dummy, *cur = head;

    while (cur && cur->next)
    {
        prev->next = cur->next;			// 1
        cur->next = cur->next->next;	// 2
        prev->next->next = cur;			// 3

        prev = cur;
        cur = cur->next;
    }

    return dummy->next;
}

19. 删除链表的倒数第 N 个结点（Medium）

要在一轮扫描中完成删除，只需使用两个指针prev，cur。cur要领先prev n个结点，保持这个距离，当cur遍历到最后一个结点，prev指向结点的下一个节点就是倒数第n个待删除的节点。

ListNode* removeNthFromEnd(ListNode* head, int n)
{
    auto dummy = new ListNode(0, head);
    ListNode *prev = dummy, *cur = dummy;

    while (n--) cur = cur->next;

    while (cur->next)
    {
        prev = prev->next;
        cur = cur->next;
    }

    ListNode* tmp = prev->next;
    prev->next = tmp->next;
    delete tmp;
    return dummy->next;
}

160. 相交链表（Easy）

两个栈从后往前找相交结点

• 时间复杂度：\(O(m+n)\)

• 空间复杂度：\(O(m+n)\)

通过分别把A，B节点压入占中，判断弹出的节点指向的地址是否相同。

ListNode* getIntersectionNode_stack(ListNode *headA, ListNode *headB)
{
    stack<ListNode*> stkA, stkB;
    ListNode* ans = nullptr;

    while (headA)
    {
        stkA.push(headA);
        headA = headA->next;
    }

    while (headB)
    {
        stkB.push(headB);
        headB = headB->next;
    }

    while (!stkA.empty() && !stkB.empty())
    {
        if (stkA.top() != stkB.top())
            break;

        ans = stkA.top();
        stkA.pop();
        stkB.pop();
    }

    return ans;
}

哈希表

• 时间复杂度：\(O(m+n)\)

• 空间复杂度：\(O(n)\)

将第一个链表的节点存放到哈希表中，遍历第二个链表，如果能在哈希表中找到相同节点，则该节点为交点。

ListNode* getIntersectionNode_hash(ListNode *headA, ListNode *headB)
{
    unordered_map<ListNode*, int> mapA;

    while (headA)
    {
        mapA[headA] = 1;
        headA = headA->next;
    }

    while (headB)
    {
        if (mapA.find(headB) != mapA.end()) return headB;

        headB = headB->next;
    }

    return nullptr;
}

对齐链表

• 时间复杂度：\(O(m+n)\)

• 空间复杂度：\(O(1)\)

分别遍历链表A，B的长度，算出长度差，选择长的链表对齐，然后继续遍历检查是否有相同的节点。

ListNode* getIntersectionNode(ListNode *headA, ListNode *headB)
{
    int lenA = 0, lenB = 0;
    ListNode *curA = headA, *curB = headB;

    while (curA)
    {
        curA = curA->next;
        lenA++;
    }

    while (curB)
    {
        curB = curB->next;
        lenB++;
    }

    curA = headA;
    curB = headB;

    if (lenA < lenB)
    {
        swap(curA, curB);
        swap(lenA, lenB);
    }

    int gap = lenA - lenB;
	
    // 先遍历长的比短的多出来的部分
    while (gap--) curA = curA->next;
	
    // 长度对齐后同时遍历找第一个相同结点
    while (curA && curB)
    {
        if (curA == curB) return curA;

        curA = curA->next;
        curB = curB->next;
    }

    return nullptr;
}

通过同时连续遍历两个链表。如：遍历A链表后，接着遍历B链表，与此同时，遍历B链表后，接着遍历A链表。

这样两个链表的遍历总长度是相同的。长度差就被补全了。

ListNode* getIntersectionNode(ListNode *headA, ListNode *headB)
{
    ListNode *curA = headA, *curB = headB;

    while (curA != curB)
    {
        curA = !curA ? headB : curA->next;
        curB = !curB ? headA : curB->next;
    }

    return curA;
}

142. 环形链表 II（Medium）

哈希表

哈希记录遍历的每个节点，第一个重复的即为尾节点指向的循环节点。

ListNode *detectCycle_hash(ListNode *head)
{
    unordered_map<ListNode*, int> nodeCount;

    while (head)
    {
        nodeCount[head]++;
        if (nodeCount[head] > 1) return head;

        head = head->next;
    }

    return nullptr;
}

快慢指针

fast 每次都被slow多走一个节点（slow的两倍速），则如果遇到循环，fast一定最后会追上slow。两个指针相遇的节点和循环开始节点的关系如下：

• slow 的路程：\(x+y\)

• fast 的路程：\(x+y+n(y+z)\;\;(n为\rm{fast}循环的圈数)\)

• fast 的路程是 slow 的两倍

\[ \begin{align} (x+y)\times 2 & =x+y+n(y+z) \\ x+y & = n(y+z) \\ x & = (n-1)(y+z)+z \end{align} \]

所以\(x\)等于\(n-1\)圈循环加上一个\(z\)。因此可以用两个指针分别从 相遇点 和 起点 触发，相遇点为环的进入点。

ListNode *detectCycle(ListNode *head)
{
    ListNode *fast = head, *slow = head;

    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            // 起点和相遇点
            ListNode *p1 = head, *p2 = fast;

            while (p1 != p2)
            {
                p1 = p1->next;
                p2 = p2->next;
            }

            return p1;
        }
    }
    return nullptr;
}