[数据结构与算法]Leetcode总结——2.链表

单链表

Leetcode707.设计链表

class MyLinkedList {
    public:
    struct Node{
         int val;
         Node *next;
         Node (int x):val(x),next(NULL){}
    };
    int size;
    Node *head;

    MyLinkedList() {
       //初始化一个头结点head,相当于定义了一个空结点作为保护节点，本身不算节点
       head=new Node(0);
       //链表长度
       size=0;

    }
    
    int get(int index) {
        if(index<0||index>=size)return -1;
        Node *cur=head->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        Node *newNode =new Node(val);
        newNode->next=head->next;
        head->next=newNode;
        size++;
    }
    
    void addAtTail(int val) {
         Node *newNode=new Node(val);
         Node *cur =head;
         while(cur->next!=NULL){
             cur=cur->next;
         }
         newNode->next=cur->next;
         cur->next=newNode;
         size++;

    }
    
    void addAtIndex(int index, int val) {
        if(index<=0){
            addAtHead(val);
        }else if(index==size){
            addAtTail(val);
        }else if(index>size){
            return;
        }else{
            Node *newNode=new Node(val);
            Node *cur=head;
            while(index--){
               cur=cur->next;
            }
            newNode->next=cur->next;
            cur->next=newNode;
            size++;
        }
    }
    
    void deleteAtIndex(int index) {

         if(index<0||index>=size)return;

         Node *cur=head;

         while(index--){
             cur=cur->next;
         }
         cur->next=cur->next->next;
         size--;
    }
   
};

双链表

Leetcode707.设计链表

class MyLinkedList {
public:
    struct Node{
        int val;
        Node *next;
        Node *prev;
        Node(int x):val(x),prev(NULL),next(NULL){}
    };

    int size;
    Node *head;
    Node *tail;

    MyLinkedList() {
        size=0;
        head=new Node(0);
        tail=new Node(0);
        head->next=tail;
        tail->prev=head;
    }
    
    ~MyLinkedList(){
        delete head;
        delete tail;
    }

    int get(int index) {
        if(index<0||index>=size)return -1;
        Node *cur=head->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        Node *newNode =new Node(val);
        newNode->next=head->next;
        head->next->prev=newNode;
        head->next=newNode;
        newNode->prev=head;
        size++;
    }
    
    void addAtTail(int val) {
        Node *newNode =new Node(val);
        tail->prev->next=newNode;
        newNode->prev=tail->prev;
        newNode->next=tail;
        tail->prev=newNode;
        size++;
        

    }
    
    void addAtIndex(int index, int val) {
        if(index<=0){
            addAtHead(val);
        }else if(index==size){
            addAtTail(val);
        }else if(index>size){
            return;
        }else{
             Node *cur=head;
             Node *newNode=new Node(val);
             while(index--){
                 cur=cur->next;
             }
             newNode->next=cur->next;
             cur->prev=newNode;
             cur->next=newNode;
             newNode->prev=cur;
             size++;

        }
       
    }
    
    void deleteAtIndex(int index) {
         if(index<0||index>=size)return;

             Node *cur=head;
             
             while(index--){
                 cur=cur->next;
             }
             cur->next->next->prev=cur;
             cur->next=cur->next->next;
             size--;

    }
};

链表的初始化:
为了防止链表为空时进行访问出错，添加节点作为保护节点
单链表添加head节点
双链表添加head tail两个节点

注意链表进行翻转等操作时，由于链表最后一个结点指向空，实际要修改n条边而不是n-1条。

206.反转链表
25.k个一组翻转链表
141.环形链表
142.环形链表Ⅱ