前言

这是小老弟学习 leetcode 链表题的笔记，希望对大家有所帮助，如果喜欢，点个赞再走吧😊

leetcode 203 移除链表元素

题目链接

传送门：https://leetcode-cn.com/problems/remove-linked-list-elements/

我的题解

题目描述

给你一个以 head 开头的链表和值为 val 的整数，请你删除链表中所有满足 Node.val == val 的节点，并返回新节点。

样例

算法

（遍历） $O (n)$

由于题目可能变动头结点，故申请一个虚拟节点 dummy_node，然后删除所有值为 val 的节点即可。记得删除之后要释放内存以及释放自己申请的内存。

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* cur = dummy_head;

        while (cur->next) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else cur = cur->next;
        }
        
        head = dummy_head->next;
        delete dummy_head;

        return head;
    }
};

leetcode 707 设计链表

题目链接

传送门：https://leetcode-cn.com/problems/design-linked-list/

我的题解

题目描述

题目要求设计出一个链表，可以是单链表，也可以是双链表，这里我选择设计单链表。要求实现以下功能：

get(index)：获取第 index 个节点的值，如果索引无效，返回 -1.
addAtHead(val)：将值为 val 的节点插入到链表头。
addAtTail(val)：将值为 val 的节点插入到链表尾。
addAtIndex(index, val)：将值为 val 的值插入到链表中第 index 个节点的位置，如果 index < 0 ，则插入头部，如果 index == size ，插入到尾部，如果 index > size ，无效插入。
deleteAtIndex(Index)：删除链表中第 index 个节点。

样例

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

算法

具体见代码：

class MyLinkedList {
public:
    struct MyLinkedNode {
        int m_val;
        MyLinkedNode* m_next;

        MyLinkedNode(int val) : m_val(val), m_next(nullptr) {}
    };
    /* initialize the linked list */
    MyLinkedList() {
        m_size = 0;
        m_dummy_head = new MyLinkedNode(-1);
    }
    /* get the value of node at the index */
    int get(int index) {
        if (index < 0 || index > m_size - 1) return -1;

        MyLinkedNode* cur = m_dummy_head->m_next;
        for (int i = 0; i < index; ++i) 
            cur = cur->m_next;

        return cur->m_val;
    }
    /* add node to the head */
    void addAtHead(int val) {
        MyLinkedNode* new_head_node = new MyLinkedNode(val);

        new_head_node->m_next = m_dummy_head->m_next;
        m_dummy_head->m_next = new_head_node;
        ++m_size;
    }
    /* add node to the tail */
    void addAtTail(int val) {
        MyLinkedNode* insert_pos = m_dummy_head;
        while (insert_pos->m_next != nullptr) insert_pos = insert_pos->m_next;
        
        MyLinkedNode* new_tail_node = new MyLinkedNode(val);

        insert_pos->m_next = new_tail_node;
        ++m_size;
    }
    /* add a node at the specified location */
    void addAtIndex(int index, int val) {
        if (index > m_size) return;

        MyLinkedNode* insert_pos = m_dummy_head;
        while (index--) insert_pos = insert_pos->m_next;

        MyLinkedNode* new_node = new MyLinkedNode(val);

        new_node->m_next = insert_pos->m_next;
        insert_pos->m_next = new_node;
        ++m_size;
    }
    /* delete a node at the specified location */
    void deleteAtIndex(int index) {
        if (index < 0 || index >= m_size) return;
        MyLinkedNode* delete_pre = m_dummy_head;

        while (index--) delete_pre = delete_pre->m_next;
        MyLinkedNode* tmp = delete_pre->m_next;
        delete_pre->m_next = delete_pre->m_next->m_next;
        delete tmp;
        --m_size;
    }

private:
    int m_size;
    MyLinkedNode* m_dummy_head;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

leetcode 206 反转链表（经典题）

题目链接

传送门：https://leetcode-cn.com/problems/reverse-linked-list/

我的题解

题目描述

反转链表。

样例

算法1

（双指针） $O (n)$

链表题一定要画图，不要空想折磨自己！这道题画一画图就做出来了。

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* front = head;
        ListNode* back = head->next;

        while (back) {
            ListNode* tmp = back->next;
            back->next = front;

            front = back;
            back = tmp;
        }
        head->next = nullptr;

        return front;
    }
};

算法2

(链表操作，递归) $O (n)$

首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next) ，这样我们可以将以 head->next 为头节点的链表翻转，并得到原链表的尾节点 tail ，此时 head->next 是新链表的尾节点，我们令它的 next 指针指向 head ，并将 head->next 指向空即可将整个链表翻转，且新链表的头节点是 tail 。

空间复杂度分析：总共递归 nn 层，系统栈的空间复杂度是 $O (n)$ ，所以总共需要额外 $O (n)$ 的空间。
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是 $O (n)$ 。

y总这思路简直不要太绝！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

作者：yxc
链接：https://www.acwing.com/solution/content/316/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

题目链接

传送门：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

我的题解

题目描述

给定一个链表，要求两两交换它的元素。要求：不只是交换值。

样例

算法

（模拟） $O (n)$

还是那句话，在纸上模拟一遍，由于头结点可能发生改变，所以申请一个虚拟节点，用完记得释放。

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* dummy_node = new ListNode(-1);
        dummy_node->next = head;

        ListNode* cur = dummy_node;

        while (cur->next && cur->next->next) {
            ListNode* ne = cur->next;
            ListNode* nee = cur->next->next;

            cur->next = nee;
            ne->next = nee->next;
            nee->next = ne;

            cur = ne;
        }

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