[数据结构与算法]leetcode解题链表篇

1. 203.移除链表元素

给你一个链表的头节点?head和一个整数?val，请你删除链表中所有满足?Node.val == 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) {

        if(head == nullptr)
            return nullptr;

        // 先去除头节点

        while(head != nullptr && head->val == val ){
            ListNode * tmp = head;
            head = head->next;
            delete tmp;
        }

        // 其他节点
        ListNode * node = head;
        while(node != nullptr && node->next !=nullptr){
            if(node->next->val == val){
                ListNode * tmp = node->next;
                node->next = node->next->next;
                delete tmp;
            }else{
                node = node->next;
            }
        }

        return head;
        

    }
};

本题算是对大二所做过的练习的一些回顾，在实操的过程中，容易出现空指针的问题，所以之后编写相关的算法程序时一定要注意一些判断语句的先后顺序，如&& 前后的语句的顺序。 head != nullptr && head->val == val 举例，如果后者放在前面，那么就会出现空指针问题。

2. 707.设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val?和?next。val?是当前节点的值，next?是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性?prev?以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第?index?个节点的值。如果索引无效，则返回-1。 addAtHead(val)：在链表的第一个元素之前添加一个值为?val?的节点。插入后，新节点将成为链表的第一个节点。 addAtTail(val)：将值为?val 的节点追加到链表的最后一个元素。 addAtIndex(index,val)：在链表中的第?index?个节点之前添加值为?val? 的节点。如果?index?等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 deleteAtIndex(index)：如果索引?index 有效，则删除链表中的第?index 个节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class MyLinkedList {
public:
    MyLinkedList() {
        this->length=0;
        this->head = nullptr;
    }

    struct ListNode{

    int val;
    ListNode * next;
    ListNode():val(0),next(nullptr){}
    ListNode(int val):val(val),next(nullptr){}
    ListNode(int val,ListNode * next):val(val),next(next){}

    };

    void print(){
        ListNode * node = this->head;
        while(node!=nullptr){
            cout<<node->val<<"->";
            node = node->next;
        }
        cout<<" length" << this->length<<endl;
    }
    
    int get(int index) {
        int result = -1;
        // 索引无效
        if(index > length - 1 || index < 0){
            return result;
        }

        ListNode * node = head;
        for(int i = 0 ; i < index ; i++){
            node = node->next;
        }
        result = node->val;
        return result;
    }
    
    void addAtHead(int val) {
        ListNode * node = new ListNode(val,head);
        head = node;
        this->length++;
    }
    
    void addAtTail(int val) {
        if(this->length == 0){
            this->head = new ListNode(val,nullptr);
            this->length++;
        }else{
            ListNode * node = this->head;
            while(node->next != nullptr){
                node = node->next;
            }
            node->next = new ListNode(val,nullptr);
            this->length++;
        }
    }
    
    void addAtIndex(int index, int val) {

        if(index <= 0){
            addAtHead(val);
        }else if(index == this->length){
            addAtTail(val);
        }else if(index > 0 && index < this->length)
        {
            ListNode * node = this->head;
            for(int i = 0 ; i < index - 1 ; i++)
                node = node->next;
            ListNode * newNode = new ListNode(val,node->next);
            cout<<"head->val"<<head->val<<endl;
            node->next = newNode;
            this->length++;
        }
    }
    
    void deleteAtIndex(int index) {
        if(index >0 && index < this->length){
            ListNode * node = this->head;
            for(int i = 0 ; i < index - 1 ; i++){
                node = node->next;
            }
            node->next = node->next->next;
            this->length--;
        }else if(index == 0){
            this->head = this->head->next;
            this->length--;
        }

    }

private:
    ListNode * head;
    int length;
};

/**
 * 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);
 */

这题难度不大，但是一些细节方面及其麻烦，比如调用对象的方法或属性的时候，一定要先判断好这个对象是否可能为空，再就是一些细节上的东西，花了我挺多时间去debug的。

3. 206.反转链表

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

/**
 * 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) {
        
        ListNode * node = head;
        ListNode * before = nullptr;
        while(node != nullptr){
            ListNode * tmp = node->next;
            node->next = before;
            before = node;
            if(tmp != nullptr){
                cout<<"11";
                node = tmp;
            }else{
                cout<<"22";
                head = node;
                node = tmp;
            }
        }

        return head;
    }
};

本题我的思路就是用一个before变量存着前一个节点的指针，然后不停地更新before；由于当前正在操作的node节点的next会变，所以在对其进行操作之前先用tmp变量将该节点最初指向的节点的指针给存下来。直到遍历完这个链表即可完成反转。

也可以看成是双指针法

本题还有一种做法是递归法，之后有兴趣可以看看。

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

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

/**
 * 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 == nullptr || head->next == nullptr)
            return head;

        ListNode *node = head;
        ListNode *before = nullptr;

        while (node != nullptr && node->next != nullptr)
        {
            if (node == head)
            {
                ListNode *tmp = node->next;
                node->next = node->next->next;
                tmp->next = node;
                head = tmp;
                before = node;
                cout<<"before->val "<<before->val<<endl;
            }
            else
            {
                ListNode *tmp = node->next;
                node->next = node->next->next;
                tmp->next = node;
                before->next = tmp;
                before = node;
                cout<<"before->val "<<before->val<<endl;
            }
            node = node->next;
        }

        return head;
    }
    
};

思路： 首先是做一个判断，剔除掉只有1个和2个节点的链表，然后由于是两两交换，所以判断当前节点node和下一个节点node->next不为空 即可，再维护一个before变量来存储上一个节点的指针（因为这是一个单链表）每次循环更新before的值。两个两个一组来进行交换。

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

给你一个链表，删除链表的倒数第?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* removeNthFromEnd(ListNode* head, int n) {
                int length = 0;
        ListNode *node = head;
        while (node != nullptr)
        {
            length++;
            node = node->next;
        }
        cout<<length;

        if(n == length){
            head = head->next;
            return head;
        }

        
        ListNode *tmp = head;
        for(int i = 0 ; i < length - n - 1 ; i++){ // length - 2
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;
        return head;
    }
};

// 一次扫描的做法
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

扫描两次直接不难了，硬做就行。而一次扫描的做法就比较巧妙一点，利用的是双指针的思想，设置快、慢两个指针，快指针先往后走n个节点，保持两个指针之间的距离为n从而达到题目要求的倒数第n个的要求

6. 02.07. 链表相交

给你两个单链表的头节点?headA和?headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回?null?。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;
        ListNode *result = nullptr;

        unordered_map<ListNode*,int> map;

        while(node1!=nullptr){
            map[node1] = 1;
            node1 = node1->next;
        }
        while(node2!=nullptr){
            if(map.count(node2) == 1){
                result = node2;
                break;
            }
            node2 = node2->next;
        }
        return result;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int cntA=0,cntB=0;
        ListNode *trackA=headA, *trackB=headB;
        while(trackA!=nullptr){trackA=trackA->next;cntA++;}
        while(trackB!=nullptr){trackB=trackB->next;cntB++;}
        if(cntA>cntB){while(cntA-cntB>0){headA=headA->next;cntA--;}}
        if(cntB>cntA){while(cntB-cntA>0){headB=headB->next;cntB--;}}
        while(headA!=nullptr){
            if(headA==headB){return headA;}
            headA=headA->next;
            headB=headB->next;
        }
        return nullptr;

    }
};

这题硬做的话，不难，利用了哈希的思想，把A链表的节点全部存储，然后再遍历B节点判断是否有相同的，这题不适合用双指针，双指针只适合于有序的情况。第二种思路是利用了链表相交后的长度相等，先计算出两个链表的长度，求得差值，之后让两个链表指针指向同样长度节点，即尾部对齐，这样的话就能够在while循环中同时移动A、B的指针了。（方法二O(1)空间）

7. 142.环形链表II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*,int> map;
        ListNode *node = head;
        while(node!=nullptr){
            if(map.count(node) == 1){
                return node;
            }
            map[node] =1;
            node = node->next;
        }
        return nullptr;
    }
};

// 方法二
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode *fast = head;
        ListNode *slow = head;

        while(fast!=nullptr &&  fast->next !=nullptr && slow!=nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){ //有环存在
                
                ListNode * tmp = head;
                while(tmp != slow){
                    tmp = tmp->next;
                    slow = slow->next;
                }
                return tmp;

            }

        }
        return nullptr;

    }
};

方法一硬做也能过，同样是用哈希表存储

方法二 O(1)空间，主要是利用了环追及问题的思路，详见https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/