链表这东西真的学一阵忘一阵😂

单向链表

结构定义

节点结构 ListNode
值 data
指向下一个节点的指针 next

struct ListNode{
    int data;
    ListNode* next;
    ListNode(int x):data(x),next(nullptr){}
}Node;

基本操作

创建链表

定义单链表类，封装基本操作。下面的几个操作都在public里~

class LinkedList{
public:
    ListNode* head;
    LinkedList():head(nullptr);
}

插入节点

头插法:新节点加到链表头部

void insertAtHead(int data){
    ListNode* newNode=new ListNode(data);
    newNode->next=head;
    head=newNode;
}

尾插法：:新节点加到链表尾部

void insertAtTail(int data){
    ListNode* newNode=new ListNode(data);
    if(!head){
        head=newNode;
        return;
    }
    ListNode* temp=head;
    while(temp->next){
        temp=temp->next;
    }
    temp->next=newNode;
}

删除节点

void deleteNode(int data){
    if(!head){
        return;
    }
    if(head->data==data){
        ListNode* temp=head;
        head=head->next;
        delete temp;
        return;
    }
    ListNode* temp=head;
    while(temp->next && temp->next->val !=val){
        temp=temp->next;
    }
    if(temp->next){
        ListNode* delNode=temp->next;
        temp->next=temp->next->next;
        delete delNode;
    }
}

修改节点

void updateNode(int oldData,newData){
    ListNode* temp=head;
    while(temp){
        if(temp-data==oldData){
            temp->data==oldData;
            return;
        }
        temp=temp->next;
    }
}

查找节点

bool searchNode(int data){
    ListNode* temp=head;
    while(temp){
        if(temp->data==data){
            return true;
        }
    }
    return false;
}

打印链表

void printList(){
    ListNode* temp=head;
    while(temp){
        cout<<temp->val<<"->";
        temp=temp->next;
    }
    cout<<"NULL"<<endl;
}

释放链表内存

~LinkedList(){
    while(head){
        ListNode* temp=head;
        head=head->next;
        delete temp;
    }
}

83.删除排序链表中的重复元素

给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

提示：

链表中节点数目在范围 [0, 300] 内

-100 <= Node.val <= 100

题目数据保证链表已经按升序排列

解题思路

【如果】头节点=空：直接返回该节点
初始化一个当前节点变量=头节点
【只要】当前节点->next不为空

「如果」当前节点->next的值=当前节点的值： 当前节点->next=当前节点->next->next
「否则」当前节点=当前节点->next

返回头节点

完整代码

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head==nullptr){
            return head;
        }
        ListNode* cur=head;
        while(cur->next!=nullptr){
            if(cur->next->val==cur->val){
                cur->next=cur->next->next;
            }
            else{
                cur=cur->next;
            }
        }
        return head;
    }
};