链表

删除单向链表中的指定节点

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

只能访问当前节点，当前节点不是末尾节点

借尸还魂：将当前节点的值和 next 全部更新为其 next，再删除 next

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

移除未排序链表中的重复节点

遍历的同时使用 map 记录；

或者

使用双指针，current 用于迭代，runner 用于检查后续节点有无重复

寻找链表中倒数第 K 个元素

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

快慢指针

删除链表中某个节点，只能访问该节点，不能访问 head

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

删除后续节点，并将后续节点的值复制到该节点

链表的加法，数字反向存放

https://leetcode-cn.com/problems/add-two-numbers/

迭代，记录进位

链表的加法，数字正向存放

https://leetcode-cn.com/problems/add-two-numbers-ii/

1. 对短的链表补 0
2. 封装 pair 结构记录 ListNode 和进位
3. 递归求解

判断链表是否有环

https://leetcode-cn.com/problems/linked-list-cycle/

双指针必相遇

判断有环链表的环路起始点

https://leetcode-cn.com/problems/linked-list-cycle-ii/

假如链表起点距离环路起点为 k

1. 创建双指针：fast 和 slow；slow 每走一步，fast 走两步
2. 两者相碰时的节点必然距离环路起点 k
3. slow 重置到 head，再以相同的速度移动 slow 和 fast 相碰时必是环路起点

两个链表的相交节点

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

双指针：先得到两个链表的长度，然后得到长度的差值 distance，两个指针分别从两个链表头部遍历，其中较长链表指针先走 distance 步，然后同时向后走，当两个指针相遇的时候，即链表的交点

链表的中间节点

https://leetcode-cn.com/problems/middle-of-the-linked-list/

// 1->2->3->4 则返回 3；1->2->3 则返回 2
ListNode* middleNode(ListNode* head) {
    ListNode *fast = head, *slow = head;

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

    return slow;
}

反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

反转链表的递归解法非常直观；

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

    ListNode *next = head->next;
    // reverseList 作用：传入 1->2->3，结果为 1<-2<-3，并返回 3
    ListNode *after = reverseList(next);
    next->next = head;
    head->next = NULL;
    return after;
}

迭代解法

ListNode *reverseList(ListNode *head)
{
    ListNode *last = nullptr;
    ListNode *cur = head;
    while (cur)
    {
        ListNode *next = curNode->next;
        cur->next = last;
        last = cur;
        cur = next;
    }
    return last;
}

判断是否回文链表

https://leetcode-cn.com/problems/palindrome-linked-list/

1. 寻找后半部分的起点
2. 反转后半部分链表
3. 双指针比较前半部分和后半部分的是否相同