链表相关算法

注意

链表的使用中可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了
链表的使用要注意使用p=p->next;因为p为nullptr时，p->next会造成内存溢出
注意移除链表元素后删除元素，回收空间

203.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 ListNode *removeElements(ListNode *head, int val)
{
    ListNode *L = new ListNode();
    L->next = head;//使用头节点可以让
    ListNode *p = L;
    ListNode *q;
    p = L;
    while (p->next)
    {
        if (p->next->val == val)
        {
            q=p->next;
            p->next = p->next->next;
            delete q;//删除元素回收空间
        }
        else
        {
            p = p->next;
        }
    }
    return L->next;
}

206. 反转链表

链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]

虚拟头节点

遍历整个链表，基于头插法的思想重新构建链表

ListNode *reverseList(ListNode *head)
{
    ListNode *L =new ListNode();
    ListNode *p =new ListNode();
    ListNode *q =new ListNode();
    p=head;
    while(p){
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    }
    return L->next;
}

双指针法

利用双指针，遍历修改，例如原本节点的关系为 pre->cur 双指针修改为 pre<-cur

ListNode *reverseList(ListNode *head)
{
    ListNode *pre=nullptr;
    ListNode *cur=head;
    while(cur){
        ListNode *temp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=temp;
    }
    return pre;//最后cur指向了空指针，pre指向了原本的最后一个节点
}

24. 两两交换链表中的节点

题目链接

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]

ListNode *swapPairs(ListNode *head)
{
    ListNode *L = new ListNode();
    L->next = head;
    ListNode *cur = L->next;
    ListNode *pre = L;
    while (cur && cur->next)
    {
        ListNode *temp = pre;
        pre = cur;
        cur = cur->next;
        // 此时 temp->pre->cur->nullptr
        pre->next = cur->next;
        cur->next = pre;
        temp->next = cur;
        // 此时 temp->cur->pre

        cur = pre->next;
    }
    return L->next;
}

19.删除链表的倒数第N个节点

题目链接

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：一次扫描实现
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]

双指针

思路：要求删除第n个节点，那么设置快慢两个指针，二者相差为n+1，同时遍历，当快指针遍历完时，慢指针即为倒数第n-1个节点

ListNode *removeNthFromEnd(ListNode *head, int n)
{
    ListNode *L = new ListNode();
    L->next = head;
    ListNode *fast = L;
    ListNode *slow = L;
    int num = n + 1;
    while (num > 0)
    {
        fast = fast->next;
        num--;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = fast->next;
    delete fast;
    return L->next;
}

面试题 02.07. 链表相交

题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

思路

可以计算出两个链表的长度，然后每个链表都有一个对应的指针，使指向的节点到链表末尾的链表长度相等

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    int numa = 0, numb = 0;
    ListNode *p = headA;
    ListNode *q = headB;
    int length = 0;
    while (p)
    {
        numa++;
        p = p->next;
    }
    while (q)
    {
        numb++;
        q = q->next;
    }
    p = headA;
    q = headB;
    if (numa > numb)
    {
        length = numa - numb;
        while (length)
        {
            p = p->next;
            length--;
        }
    }
    else
    {
        length = numb - numa;
        while (length)
        {
            q = q->next;
            length--;
        }
    }
    while (p)
    {
        if (p == q)
            return p;
        p = p->next;
        q = q->next;
    }
    return nullptr;
}

142.环形链表 Ⅱ

题目链接

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路

如果链表存在环，那么设定一个每次行走2个节点的fast指针，一个每次行走1个节点的slow指针，这两个指针速度相差1，那么指针一定会在循环链表中相遇（操场跑步的时候，时间一直走，速度快的人一定会和速度慢的人相遇（套圈））

根据推导，我们可以看出如果重新设定一个从head节点出发的指针，一个从fast和slow节点相遇的结点出发的指针，两个指针的移动速度相同，他们一定会在环的入口处相遇

ListNode *detectCycle(ListNode *head)
{
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            fast = head;
            while (fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return nullptr;
}