LeetCode 题解随笔：链表篇

目录

一、链表基础 *** 作

203.移除链表元素

707.设计链表

二、双指针法

206.反转链表

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

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

面试题 02.07. 链表相交

142.环形链表II

---

一、链表基础 *** 作 203.移除链表元素

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* newHead = new ListNode();
        newHead->next = head;
        ListNode* p = newHead;
        while (p->next != NULL)
        {
            if (p->next->val == val) {
                //删除链表记得释放空间
                ListNode* temp = p->next;
                p->next = p->next->next;
                delete temp;
            }
            else {
                p = p->next;
            }
        }
        head = newHead->next;
        //释放虚拟头节点
        delete newHead;
        return head;
    }
};

本题对于打好链表基础非常重要，尤其是最开始链表的定义。其包括数值、next指针（仍为链表类型）和构造函数。

本体采用了虚拟头节点方法保持了删除链表第一个元素时的 *** 作与删除其它元素的 *** 作一致。须注意一下几点：

1.删除元素记得释放空间；

2.返回head指针要让head=newHead->next；

3.记得释放虚拟头节点的空间。

707.设计链表

class MyLinkedList {
public:
    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) {}
    };

    MyLinkedList() {
        //虚拟头节点
        this->m_Head = new ListNode();
        this->m_Size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= this->m_Size) {
            return -1;
        }
        ListNode* p = this->m_Head;
        for (int i = 0; i <= index; i++) {
            p = p->next;
        }
        int res = p->val;
        return res;
    }

    void addAtHead(int val) {
        ListNode* elem = new ListNode(val);
        elem->next = this->m_Head->next;
        this->m_Head->next = elem;
        this->m_Size++;
    }

    void addAtTail(int val) {
        ListNode* elem = new ListNode(val);
        ListNode* p = this->m_Head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = elem;
        this->m_Size++;
    }

    void addAtIndex(int index, int val) {
        if (index > this->m_Size) {
            return;
        }
        else if (index <= 0) {
            addAtHead(val);
            this->m_Size++;
        }
        else {
            ListNode* elem = new ListNode(val);
            ListNode* p = this->m_Head;
            for (int i = 0; i < index; i++) {
                p = p->next;
            }
            elem->next = p->next;
            p->next = elem;
            this->m_Size++;
        }
    }

    void deleteAtIndex(int index) {
        if (index >= 0 && index < this->m_Size) {
            ListNode* p = this->m_Head;
            while (index--) {
                p = p->next;
            }
            ListNode* temp = p->next;
            p->next = temp->next;
            delete temp;
            this->m_Size--;
        }
        else {
            return;
        }
    }

    ~MyLinkedList() {
        if (this->m_Head != NULL) {
            delete this->m_Head;
            this->m_Head = NULL;
        }
    }

private:
    ListNode* m_Head;
    int m_Size;
};

都是链表的基础 *** 作，添加和删除不要忘记修改size属性。

---

二、双指针法 206.反转链表

class MyLinkedList {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* temp = NULL;
        while (cur != NULL) {
            //保存下一个节点
            temp = cur->next;
            //进行翻转
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

 用两个指针完成反转，过程参考上图（来源：代码随想录）。初始cur指向头节点，pre指向NULL。利用temp保存下一个节点的信息后，完成当前两个节点的反转。

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

class MyLinkedList {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* newHead = new ListNode();
        newHead->next = head;
        ListNode* p = newHead;
        while (p->next != NULL && p->next->next != NULL) {
            ListNode* second = p->next;
            ListNode* first = second->next;
            p->next = first;
            second->next = first->next;
            first->next = second;
            p = second;
        }
        return newHead->next;
    }
};

理解虚拟头指针的作用，一旦定义了虚拟头指针，返回值最好为newHead->next而不是原来的head。交换时按照从左到右的顺序依次进行即可。

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

class MyLinkedList {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count = 0;
        ListNode* newHead = new ListNode();
        newHead->next = head;
        ListNode* fast = newHead;
        ListNode* slow = newHead;
        //快慢指针相差n
        for (; count < n; count++){
            fast = fast->next;
        }
        //快指针指向链表最后一个元素，慢指针此时指向待删除元素的前一个元素
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        delete temp;
        return newHead->next;
    }
};

这是双指针法的一个非常重要的应用。让快指针比慢指针领先n个位置，再同时移动两个指针，快指针移动至链表最后一个元素时，慢指针就在待删除元素的前一个元素。从而可以利用一次遍历实现删除。

面试题 02.07. 链表相交

class MyLinkedList {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        //求链表A、B的长度
        int sizeA = 0;
        int sizeB = 0;
        ListNode* pA = headA;
        while (pA != NULL) {
            pA = pA->next;
            sizeA++;
        }
        ListNode* pB = headB;
        while (pB != NULL) {
            pB = pB->next;
            sizeB++;
        }
        //让pA指向最长链表
        pA = headA;
        pB = headB;
        if (sizeB > sizeA) {
            swap(pA, pB);
            swap(sizeA, sizeB);
        }
        //对齐并开始寻找重合点
        int deltaL = sizeA - sizeB;
        while (deltaL--)
        {
            pA = pA->next;
        }
        while (pA != NULL) {
            if (pA == pB) {
                return pA;
            }
            pA = pA->next;
            pB = pB->next;
        }
        return NULL;
    }
};

先求两个链表的长度，末端对齐后，从对齐处开始查找重合点。重合意味着地址相同。

头节点指向的就是第一个元素，head->next指向的是第二个元素，这要和虚拟节点区分清楚。

142.环形链表II

class MyLinkedList {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* newHead = new ListNode();
        newHead->next = head;
        ListNode* fast = newHead;
        ListNode* slow = newHead;
        while (fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {
                ListNode* index1 = newHead;
                ListNode* index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};

本题技巧性较强，快指针每次走两步，慢指针每次走一步，若存在环，入环后快指针总能逼近慢指针。由于快指针每次走两步，需要以fast->next != NULL && fast->next->next != NULL作为循环条件！

入口位置的确定可以通过下图来说明（图片来源：代码随想录）

 相遇时两个指针走过的路程存在如下关系：2（x+y）=x+n*（y+z）+y

化简可得环形入口节点位置x=（n-1）y+nz。

这个式子说明，若定义一个index1在头节点，index2在相遇节点，头节点移动到x位置时，index2运行了n次z路程和（n-1）次y路程，也正好到达环形的入口位置。