链表专题-删除,设计,反转链表

发布时间:2024年01月12日

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
    if(head==nullptr)
       return nullptr;
    ListNode*nhead=new ListNode;
    nhead->next=head;
     ListNode*p=nhead;
      ListNode*del;
     while(p->next!=nullptr)
     {
        if(p->next->val==val)
         {
             del=p->next;
             p->next=del->next;
             delete del;
             del=nullptr;
         }
         else 
         {
             p=p->next;
         }
     }
     return nhead->next;
    }
};

新建一个头节点,方便指针操作。

typedef struct MyLinkedList {
    int val;
    struct MyLinkedList *next;
    struct MyLinkedList *prior;
} MyLinkedList;
MyLinkedList* myLinkedListCreate() {

MyLinkedList *p=(MyLinkedList *)malloc(sizeof(MyLinkedList));
if(p==NULL)
{
    return NULL;
}
p->val=0;
p->next=NULL;
p->prior=NULL;
return p;
}
int getlen(MyLinkedList* obj)
{MyLinkedList*p=obj->next;
int length=0;
while(p!=NULL)
{
    length++;
    p=p->next;
}
return length;
}
int myLinkedListGet(MyLinkedList* obj, int index) {
    if(obj==NULL)
    return -1;
    MyLinkedList* p=obj;
if(index<0||index>=getlen(obj))
{
return -1;
}
for(int i=0;i<=index;i++)
{
p=p->next;
}
return p->val;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {

MyLinkedList *p=(MyLinkedList *)malloc(sizeof(MyLinkedList));
if(p==NULL)
return ;
p->val=val;
if(obj->next==NULL&&obj->prior==NULL)
{
p->next=obj->next;
obj->next=p;
p->prior=obj;
return;
}
p->next=obj->next;
obj->next=p;
p->prior=obj;
obj->next->prior=p;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *p=(MyLinkedList *)malloc(sizeof(MyLinkedList));

if(p==NULL)
return ;
p->val=val;

if(obj->next==NULL&&obj->prior==NULL)
{
p->next=obj->next;
obj->next=p;
p->prior=obj;
return;
}
MyLinkedList *q=obj->next;
while(q->next!=NULL)
{
    q=q->next;
}
p->next=q->next;
q->next=p;
p->prior=q;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if(obj==NULL)
    {
        return;
    }
if(index>getlen(obj))
return;
 if(index<0)
{
   myLinkedListAddAtHead(obj,val); 
   return;
}
if(index==getlen(obj))
{
myLinkedListAddAtTail(obj,val);
return;
}
MyLinkedList* p=obj;
for(int i=0;i<index;i++)
{
p=p->next;
}
MyLinkedList*q=(MyLinkedList*)malloc(sizeof(MyLinkedList));
q->val=val;
q->next=p->next;
p->next=q;
q->prior=p;
q->next->prior=p;
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(obj->next==NULL)
    return ;
    MyLinkedList* k=obj;
  
if(index>=0&&index<=getlen(obj)-1)
{
    for(int i=0;i<index;i++)
    {
        k=k->next;
    }
MyLinkedList* p=k->next;
k->next=p->next;
free(p);
}
}


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

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

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
        return nullptr;
    ListNode* nhead=new ListNode;
    nhead->next=nullptr;
    ListNode* p=head;
     ListNode* q;
    while(p!=nullptr)
    {
        q=p->next;
        p->next=nhead->next;
        nhead->next=p;
        p=q;
    }
    return nhead->next;
    }
};

反转链表运用头插法,防止顺序搞错。

文章来源:https://blog.csdn.net/weixin_62518305/article/details/135553910
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。