力扣刷题-链表

对于一个链表，C++的定义如下：

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) {}
};

链表结构可由下表征：

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
输出：[]

这个题由于涉及到头节点的变动，因此可以先设置一个空的前置节点dummy，然后将dummy指向head。为了对dummy的指针指向进行保留，这里复制一个指针temp = dummy。接下来是两种情况，当temp->next->val == val，那么temp->next = temp->next->next。否则temp指针移动，temp = temp->next。

ListNode* removeElements(ListNode* head, int val)
{
    struct ListNode* dummy = new ListNode(0, head);
    struct ListNode* temp = dummy;
    while(temp->next != NULL)
    {
        if(temp->next->val == val)
        {
            temp->next = temp->next->next;
        }
        else
        {
            temp = temp->next;
        }
    }
    return dummy->next;
}

时间复杂度为$\small{O(n)}$，空间复杂度为$\small{O(1)}$。

707 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

class MyLinkedList {
public:
    // 初始化链表，大小为 0 ，头结点的值为 0
    // this指针用于访问类的成员变量和成员函数
    MyLinkedList() {
        this->head = new ListNode(0);
        this->size = 0;
    }
    // 获得指定节点的值
    int get(int index) {
        // 这里 >= size 是因为元节点的下标是 0，末尾节点的下标是 size - 1
        if (index < 0 || index >= size) {
            return -1;
        }
        // 定义一个指针 cur 指向头结点，这样不会改变head中的值
        ListNode* cur = head;
        // 遍历链表，直到遍历下标为 index 的节点
        for (int i = 0; i <= index; i++)
        {
            cur = cur->next;
        }
        return cur->val;
    }
    // 在 0 位置添加节点，就相当于在头部添加节点
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    // 在 size 位置添加节点，就相当于在末尾添加节点
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    // 在index处添加节点
    void addAtIndex(int index, int val) {
        // 如果 index 大于 size，则不添加节点
        if (index > size)
            return;
        // 如果 index 小于 0，则将 index 置为 0
        index = max(0, index);
        // 添加节点，size++
        size++;
        ListNode* temp = head;
        // 定位到 index 前一个节点
        for (int i = 0; i < index; i++)
        {
            temp = temp->next;
        }
        // 添加新的节点
        ListNode* NewNode = new ListNode(val);
        // 插入新的节点
        NewNode->next = temp->next;
        temp->next = NewNode;
    }
    void deleteAtIndex(int index) {
        //这里取 >= 是因为元节点下标是 0
        if (index < 0 || index >= size)
            return;
        size--;
        ListNode* temp = head;
        for (int i = 0; i < index; i++)
        {
            temp = temp->next;
        }
        ListNode* p = temp->next;
        temp->next = temp->next->next;
        // 释放被删除节点的内存
        delete p;
    }
private:
    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) {}
    };
    int size;
    ListNode* head;
};

206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]

这个题可以用双指针的解法。设定慢指针 slow = NULL，快指针 fast = head。现在开始遍历。设置temp = fast->head，保存fast的下一个节点。这里为了反转链表，需要将fast->next指向上一个节点slow，因此有fast->next = slow。现在反转了链表。开始移动fast和slow指针。我们先移动slow指针，由于现在slow已经完成任务，slow需要向右移动一位，也就是slow = fast。然后fast也向右移动一位，也就是fast = temp。这一轮的反转就完成了。
由于fast比slow快一格，而题目要求要返回反转后的头节点，所以fast要遍历到原链表的NULL处。

ListNode* reverseList(ListNode* head)
{
    ListNode* slow = NULL;
    ListNode* fast = head;
    while(fast != NULL)
    {
        ListNode* temp = fast->next;
        fast->next = slow;
        slow = fast;
        fast = temp;
    }
    return slow;
}

24 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]

这个题说了两两交换，那么只研究前两个节点之间的连接关系就行。这里我们为了让节点访问更方便，还是要在链表前插入一个虚拟头节点dummy。那么对于dummy和node1和node2，两两交换就是将节点dummy->node1->node2变成dummy->node2->node1，其他两两节点可依此类推。我们设定一个temp = dummy节点，想完成交换，首先让temp -> node2，然后node1 -> node3，最后node2 -> node1。然后更新temp向右移动两个节点，也就是temp = node1（此时node1已经成为了链表中第二个节点），开始下一轮循环。循环的终止条件需要注意，要把temp->next != NULL放在前面，不然如果temp->next == NULL，temp->next->next就是非法访问，会编译出错。

ListNode* swapPairs(ListNode* head)
{
    // 节点 0
    ListNode* dummy = new ListNode(0, head);
    ListNode* temp = dummy;
    // 第一个说明当链表是偶数个节点，第二个说明当链表是奇数个节点
    while(temp->next != NULL && temp->next->next != NULL)
    {
        //节点 1
        ListNode* node1 = temp->next;
        //节点 2
        ListNode* node2 = temp->next->next;
        //节点 dummy -> 节点 2
        temp->next = node2;
        //节点 1 -> 节点 3
        node1->next = node2->next;
        //节点 2 -> 节点 1
        node2->next = node1;
        //节点 temp = 节点 1 （步进两个节点）
        temp = node1;
    }
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

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]

这个题乍一看需要遍历两遍链表，第一遍遍历得到链表的大小，第二遍遍历得到需要删除的元素的位置。但是我们换个思路，将两个遍历合并成一个。这里需要用到双指针的策略。首先定义fast和slow指针，刚开始先移动fast指针，让fast和slow的距离为n个节点。然后开始同步移动fast和slow，当fast的下一位是NULL时，此时slow的下一位就是要删除的节点，这个时候就只需要slow->next = slow->next->next即可删除节点。

ListNode* removeNthFromEnd(ListNode* head, int n)
{
    // 定义快慢指针
    ListNode* fast = new ListNode(0, head);
    ListNode* slow = fast;
    // 定义临时头节点
    ListNode* dummy = fast;
    // 如果 n <= 0 无效
    if(n <= 0)
    {
        return dummy->next;
    }
    // 开始移动 fast 指针，当移动 n 步后停止
    for(int count = 1; count <= n; count++)
    {
        if(fast->next != NULL)
        {
            fast = fast->next;
        }
        // 如果 fast 下一位为空但是遍历次数还没达到 n 次说明 n 的大小超过链表大小，访问无效
        else if(count < n)
        {
            return slow->next;
        }
    }
    // 开始同步移动 fast 和 slow，如果 fast 的下一位为 NULL，说明到了链表末尾。此时 slow 的下一位就是要删除的节点
    while(fast->next != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    // 删除节点
    ListNode* temp = slow->next;
    slow->next = slow->next->next;
    delete temp;
    // 返回链表头节点
    return dummy->next;
}