代码随想录训练营Day03_链表

1.链表

1.1 定义

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

如图所示：

1.2 链表类型

单链表

如上所示

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示：

循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

1.3链表的实现

2. 链表移除元素

2.1 没有头结点的实现（按值删除）

• 这里以单链表为例，没有虚拟头节点为例
• 首先要判断头结点是否是要删除掉值，是的话让头结点指针移项head->next，之后再进行判断，直到头结点不在是需要删除的元素
• 之后就判断非头结点元素是否是需要删除的值
• cur 为当前元素，判断cur ->next是否是需要删除的元素，因为cur从头结点出发，经过上面的判定，head一定不是需要删除的元素
• 如果 cur -> next （别称为p） 是需要删除的元素，就让cur ->next 指向 cur ->next->next，并删除 p。（这里需要前提 cur存在，cur ->next也存在）。
• 如果不需要删除，cur 指向下一位

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

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

        ListNode * cur = head;

        while(cur != NULL and 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.2 有头结点的实现（按下标删除）

• 加入虚拟头结点为 -1，则头结点为 0开始

• 循环遍历，每次num++

• 如果num == index，会先设立一个临时指针，存储需要删除的元素的指针，然后令前一个节点的 next 等于需要删除节点的下一个，之后释放需要删除的节点。

  MyLinkedList* tmp2 = tmp->next; // 存储需要释放节点的指针
  tmp->next = tmp ->next ->next; // 令前一个节点的next等于需要删除的下一个节点
  free(tmp2); // 释放 需要删除节点
  obj->size--; // 长度--

• 删除图示：
  

#include <bits/stdc++.h>
using namespace std;

typedef struct MyLinkedList{
    int val;
    MyLinkedList * next;
    int size;
} MyLinkedList;


void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index < 0 or index >= obj->size) {
        return;
    }
    MyLinkedList* tmp = obj;
    int num = -1;
    while(true) {
        num++;
        if(num==index) {
            MyLinkedList* tmp2 = tmp->next;
            tmp->next = tmp ->next ->next;
            free(tmp2);
            obj->size--;
            return;
        }
        tmp = tmp ->next;
    }
}

3.链表设计（单链表）

3.1 重点：关于malloc使用问题

大家考虑过初始化链表，或者增加节点时，必须使用malloc函数分配空间，而不是声明一个LinkNode 变量，把地址赋予next指针呢？

考虑一下，我一开始掉井坑了，这样写的代码。

这里我的主要想法是，输入一个num，给头结点依次顺序输入val，再依次增加节点，没有使用malloc函数。

但是这里有一个重要的基础知识！！！

大家是否记得，在函数体内声明的变量，在函数调用完毕后会进行回收，而malloc分配的内存空间必须手动释放，否则不会被销毁，这就是这俩的区别！！！

假如说，使用下面的代码循环创建节点，会导致节点内存地址是有，但是里面的内容都会被释放。

// 初始化一个链表
void CrateLinkNode(LinkNode * head,int num) {

    LinkNode * p = head; // 记录虚拟头结点的临时变量
    for(int i = 0; i < num;++i) {
        int number;cin >> number;
        LinkNode tmp;
        tmp.next =NULL;
        tmp.val = number;
        p->next = &tmp;
        p = &tmp;
    }
    
}

编写测试代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef struct LinkNode
{
    int val;
    LinkNode * next;
    /* data */
} * linkNodelink;

// 初始化虚拟头结点
LinkNode * LinkNodeInit() {
    // 创建实例
    LinkNode * head;
    LinkNode p;
    p.next = NULL;
    p.val = -1;
    head = &p;
    return head;
}

// 初始化一个链表
void CrateLinkNode(LinkNode * head,int num) {

    LinkNode * p = head; // 记录虚拟头结点的临时变量
    for(int i = 0; i < num;++i) {
        int number;cin >> number;
        LinkNode tmp;
        tmp.next =NULL;
        tmp.val = number;
        p->next = &tmp;
        p = &tmp;
    }
    
}
int main () {

    LinkNode * dymyHead = LinkNodeInit();
    int num;cin >> num;
    CrateLinkNode(dymyHead,num);
    LinkNode * tmp = dymyHead;
    
    while(tmp->next != NULL) {
        cout << tmp->next->val << endl;
        tmp = tmp -> next;
    }
    return 0;

}

这里打印下链表结果：

可以发现打印结果为垃圾数字。

这里正确的写法应该为：

使用malloc分配内存空间！！！！

#include <bits/stdc++.h>
using namespace std;
typedef struct LinkNode
{
    int val;
    LinkNode * next;
    /* data */
} * linkNodelink;


// 初始化虚拟头结点
LinkNode * LinkNodeInit() {
    // 创建实例
    LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode));
    head->next = NULL;  
    return head;
}

// 初始化一个链表
LinkNode * CrateLinkNode(LinkNode * head,int num) {
    LinkNode * p = head;
    for(int i = 0; i < num;++i) {
       LinkNode * tmp = (LinkNode *)malloc(sizeof(LinkNode));
       int number;cin >> number;
       tmp->val = number;
       tmp->next = NULL;
       head->next = tmp;
       head = tmp;
    }
    return p;
}
// 打印链表
void printLinkNode(LinkNode * head) {
    LinkNode * tmp = head;
    while(tmp->next != NULL) {
        cout << tmp->next->val << endl;
        tmp = tmp -> next;
    }
    
}
// 移除链表 元素
void deleteItemLinkNode(LinkNode * head,int deleteNum) {
    LinkNode * tmp = head;

    while(tmp->next != NULL) {       
        if(tmp->next->val == deleteNum) {
             LinkNode * tmp1 = tmp->next;
             tmp->next = tmp -> next -> next;
             free(tmp1);
             continue;
        }
        tmp = tmp -> next;
    }
}

int main () {

    LinkNode * dymyHead = LinkNodeInit();
    int num;cin >> num;

    dymyHead =  CrateLinkNode(dymyHead,num);
    printLinkNode(dymyHead);
    deleteItemLinkNode(dymyHead,2);
    printLinkNode(dymyHead);

    return 0;

}

3.2 设计链表

1.初始化链表

typedef struct MyLinkedList{
    int val;
    MyLinkedList * next;
    int size;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList * dymthead = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    dymthead->next =NULL;
    dymthead->size = 0;
    return dymthead;
}

2.头插法

// 头插法
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    p->next = obj->next;
    obj->next = p;
    obj->size++;

}

3.尾插法

// 尾插法
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    obj->size++;
    MyLinkedList* tmp = obj;
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    p->next = NULL;
    while(true) {
        if(tmp -> next != NULL) {
            tmp = tmp->next;
        } else {
            tmp ->next = p;
            break;
        }
    }
}

4.按下标插入（下标的前一个位置插入）

// 按序号插入
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList* tmp = obj;
    if(index < 0 or index >= obj->size) {
        return;
    }
    if(index == obj->size - 1) {
        myLinkedListAddAtTail(obj,val);
        return;
    }
    if(index == 0) {
        myLinkedListAddAtHead(obj,val);
        return;
    }
    int num = -1;
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    while(true) {
        num++;
        
        if(num == index) {
            p->next = tmp ->next;
            tmp ->next = p;
            obj->size++;
            return;
        }
        tmp = tmp ->next;


    }

}

5.按下标删除

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index < 0 or index >= obj->size) {
        return;
    }
    MyLinkedList* tmp = obj;
    int num = -1;
    
    while(true) {
        num++;
        if(num==index) {
            MyLinkedList* tmp2 = tmp->next;
            tmp->next = tmp ->next ->next;
            free(tmp2);
            obj->size--;
            return;
        }
        tmp = tmp ->next;
    }
}

6.释放整个链表

void myLinkedListFree(MyLinkedList* obj) {
   
    while (obj != NULL)
    {   
         MyLinkedList* tmp = obj;
         obj = obj->next;
         free(tmp);
    }
    
    
}

7.打印链表

void printList( MyLinkedList* head) {
    MyLinkedList* tmp = head;
    cout <<"长度：" << head -> size << endl;
    while(tmp -> next != NULL) {
        cout << tmp -> next -> val << " ";
        tmp = tmp -> next;
        
    }
    cout << "\n";
}

8.完整代码

#include <bits/stdc++.h>
using namespace std;

typedef struct MyLinkedList{
    int val;
    MyLinkedList * next;
    int size;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList * dymthead = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    dymthead->next =NULL;
    dymthead->size = 0;
    return dymthead;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    if(obj -> size < index or index < 0) {
        return (-1);
    } 
    MyLinkedList* tmp = obj;
    int num = -1;
    while(true) {  
        num++;
        tmp = tmp->next;
        if(num == index) {
            return (tmp->val);
        }
    }

}
// 头插法
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    p->next = obj->next;
    obj->next = p;
    obj->size++;

}

// 尾插法
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    obj->size++;
    MyLinkedList* tmp = obj;
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    p->next = NULL;
    while(true) {
        if(tmp -> next != NULL) {
            tmp = tmp->next;
        } else {
            tmp ->next = p;
            break;
        }
    }
}
// 按序号插入
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList* tmp = obj;
    if(index < 0 or index >= obj->size) {
        return;
    }
    if(index == obj->size - 1) {
        myLinkedListAddAtTail(obj,val);
        return;
    }
    if(index == 0) {
        myLinkedListAddAtHead(obj,val);
        return;
    }
    int num = -1;
    MyLinkedList* p = ( MyLinkedList*)malloc(sizeof(MyLinkedList));
    p->val = val;
    while(true) {
        num++;
        
        if(num == index) {
            p->next = tmp ->next;
            tmp ->next = p;
            obj->size++;
            return;
        }
        tmp = tmp ->next;


    }

}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index < 0 or index >= obj->size) {
        return;
    }
    MyLinkedList* tmp = obj;
    int num = -1;
    
    while(true) {
        num++;
        if(num==index) {
            MyLinkedList* tmp2 = tmp->next;
            tmp->next = tmp ->next ->next;
            free(tmp2);
            obj->size--;
            return;
        }
        tmp = tmp ->next;
    }
}

void myLinkedListFree(MyLinkedList* obj) {
   
    while (obj->next != NULL)
    {   
         MyLinkedList* tmp = obj;
         obj = obj->next;
         free(tmp);
    }
    free(obj);
    
}
void printList( MyLinkedList* head) {
    MyLinkedList* tmp = head;
    cout <<"长度：" << head -> size << endl;
    while(tmp -> next != NULL) {
        cout << tmp -> next -> val << " ";
        tmp = tmp -> next;
        
    }
    cout << "\n";
}
/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/
int main () {
    MyLinkedList * head = myLinkedListCreate();
    myLinkedListAddAtHead(head,1);
    myLinkedListAddAtTail(head,2);
    printList(head);
    myLinkedListAddAtIndex(head,0,0);
    printList(head);
    myLinkedListAddAtIndex(head,1,3);
    printList(head);
    myLinkedListDeleteAtIndex(head,2);
    printList(head);

    myLinkedListFree(head);
    return 0;

}