【代码随想录算法训练Day3】LeetCode 203.移除链表元素、LeetCode 707.设计链表、LeetCode 206.反转链表

Day3 链表

链表也是一种很重要的数据结构，链表的优势是空间不必连续，分配比较自由，缺点是不支持随机访问，想要获取链表中间的某个元素，必须要从头遍历。

LeetCode 203.移除链表元素【虚拟头结点】

移除链表中的某个元素很简单，只需要把这个节点前一个节点的next指针指向这个节点后面一个元素即可。但是头结点是没有前一个节点的，此时我们有两种做法，一种是特判头结点，如果头结点元素满条件，则将头指针不断后移，其余方法不变，另一种方法是创造一个虚拟头结点，让头结点在删除时的特性与其余节点一致，而头结点的前驱就是我们创造的这个dummyhead。

解法1：头结点特判

头结点特判有一点需要注意：开头对头结点的判断要用while而不是if，因为头结点之后如果存在连续相等的值，在头结点删除后新的头结点仍满足条件，则需要全部删除。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head!=NULL && head->val==val){
            ListNode* tmp=head;
            head=head->next;
            delete tmp;
        }
        ListNode* cur=head;
        while(cur!=NULL && cur->next!=NULL){
            if(cur->next->val==val){
                ListNode* tmp=cur->next;
                cur->next=cur->next->next;
                delete tmp;
            }
            else cur=cur->next;
        }
        return head;
    }
};

解法2：虚拟头结点

这里是我的写法，其实需要在中间的判断中用临时变量获取p->next，然后delete掉，清理内存，这里没有写，以后删除需要养成良好的习惯。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy=new ListNode(0,head);
        ListNode* p=dummy;
        while(p->next!=NULL){
            if(p->next->val==val){
                p->next=p->next->next;
            }
            else p=p->next;
        }
        return dummy->next;
    }
};

LeetCode 707.设计链表【链表基础】

最考验基本功的一集，如果你仍然对链表操作有疑问，那么请回到这一题，它能解答你对所有链表基本操作的疑问。
这道题我在一开始做的时候用了数组模拟链表逃课AC了，如果题目并没有强制要求用严格的链表结构实现，有时候可以用数组模拟，这样相当于用空间换了代码复杂度。

解法1：数组模拟

class MyLinkedList {
public:
    int head,e[1010],ne[1010],idx,siz;
    MyLinkedList() {
        head=-1;
        idx=0;
        siz=0;
    }
    
    int get(int index) {
        if(index>=siz || index<0)
            return -1;
        int i=head;
        while(index--) i=ne[i];
        return e[i];
    }
    
    void addAtHead(int val) {
        e[idx]=val;
        ne[idx]=head;
        head=idx++;
        siz++;
    }
    
    void addAtTail(int val) {
        addAtIndex(siz,val);
    }
    
    void addAtIndex(int index, int val) {
        if(index>siz) return;
        if(index<=0){
            addAtHead(val);
            return;
        }
        int i=head;
        while(--index) i=ne[i];
        e[idx]=val;
        ne[idx]=ne[i];
        ne[i]=idx++;
        siz++;
    }
    
    void deleteAtIndex(int index) {
        if(index>=siz || index<0) return;
        if(index==0){
            head=ne[head];
            siz--;
            return;
        }
        int i=head;
        while(--index) i=ne[i];
        ne[i]=ne[ne[i]];
        siz--;
    }
};

解法2：链表结构

如果向上一题一样，题目已经要求使用链表结构，那就不能投机取巧了，要把基本操作好好了解一下。

class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val),next(nullptr){}
    };
    MyLinkedList() {
        dummyHead=new LinkedNode(0);
        siz=0;  
    }
    
    int get(int index) {
        if(index>(siz-1) || index<0) return -1;
        LinkedNode* cur=dummyHead->next;
        while(index--) cur=cur->next;
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode=new LinkedNode(val);
        newNode->next=dummyHead->next;
        dummyHead->next=newNode;
        siz++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode=new LinkedNode(val);
        LinkedNode* cur=dummyHead;
        while(cur->next!=NULL) cur=cur->next;
        cur->next=newNode;
        siz++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>siz) return;
        if(index<0) index=0;
        LinkedNode* newNode=new LinkedNode(val);
        LinkedNode* cur=dummyHead;
        while(index--) cur=cur->next;
        newNode->next=cur->next;
        cur->next=newNode;
        siz++;
    }
    
    void deleteAtIndex(int index) {
        if(index>=siz || index<0) return;
        LinkedNode* cur=dummyHead;
        while(index--) cur=cur->next;
        LinkedNode* tmp=cur->next;
        cur->next=cur->next->next;
        delete tmp;
        siz--;
    }

private:
    int siz;
    LinkedNode* dummyHead;
};

LeetCode 206.反转链表【双指针/递归】

反转链表也是一个非常经典的问题，它要求我们每走一步就要改变两个节点之间next指针的位置，这里有双指针法和递归法两种，得好好研究一下。

解法1：双指针

双指针解法是想法比较基础的解法，就是用一前一后两个指针，把后面的指针转到前面来。
细节：第一步cur移动前要用tmp保存cur->next，否则会丢失下一节点。
每次移动指针时，先动pre，再动cur，否则两个指针会断连。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=NULL;
        ListNode* tmp;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

解法2：递归

递归解法的本质还是双指针算法，只不过把双指针向前移动的过程转化为reverse函数中替换形参的过程，不过代码确实很简洁，当做思维扩展学了。

class Solution {
public:
    ListNode* reverse(ListNode* cur,ListNode* pre){
        if(cur==NULL) return pre;
        ListNode* tmp=cur->next;
        cur->next=pre;
        return reverse(tmp,cur);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(head,NULL);
    }
};

今日收获很多啊，对链表的理解更深了。