203.移除链表元素

1. 题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

​ image-20221017195856928

输入：head = [1,2,6,3,4,5,6], val = 6

输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1

输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7

输出：[]

2. 分析

写法1：暴力排序

注意：使用C语言和C++需要在内存中删除释放掉移除的节点。

写法1：直接使用原来的链表来进行删除操作

头节点的移除和移除其他节点是不一样的

(1) 移除头节点

(2) 移除其他节点

struct ListNode* removeElements(struct ListNode* head, int val){

 

  struct ListNode *temp;

  //1. 释放头指针

  while(head&&head->val==val)//当头指针不为空且头指针的值是需要被移除的对象时

  {

    temp=head;//把原头节点赋给temp

    head=head->next;// 将新的头结点设置为head->next并删除原来的头结点

    free(temp);//释放temp，即释放掉原来的头指针的内存

  }

  //2. 释放其他指针

  struct ListNode* cur=head;

  while(cur&&(temp=cur->next))

  {

    if(temp->val==val)//如果当前cur的下一个val是要被删除的目标

    {

      cur->next=temp->next;//那么就跳过。temp->next其实就是cur->next->next

      free(temp);//释放temp，即释放掉了要删除的目标的内存

    }

    else

    {

      cur=cur->next;//若cur->next不等于val，则将cur后移一位

    }

  }

 

  return head;

}

写法2：设置一个虚拟头结点在进行删除操作

设置一个虚拟节点，移除头节点和其他节点的操作都一样

struct ListNode* removeElements(struct ListNode* head, int val){

  //设置虚拟头节点的操作
	//需要记忆！！！
  struct ListNode *shead;
  shead=(struct ListNode *)malloc(sizeof(struct ListNode));
  shead->next=head;//头节点的下一个指向head

  //移除链表元素

  struct ListNode *cur=shead;

  struct ListNode *tmp;

  while(cur->next!=NULL)

  {

    if(cur->next->val==val)

    {

      tmp=cur->next;

      cur->next=cur->next->next;

      free(tmp);

    }

    else

    {

      cur=cur->next;

    }

  }

  head=shead->next;

  free(shead);

  return head;

}

这两种方法是处理链表的常用两种方法

707.设计链表

1. 题目

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

2. 分析

这道题目设计链表的五个接口：

  • 获取链表第index个节点的数值
  • 在链表的最前面插入一个节点
  • 在链表的最后面插入一个节点
  • 在链表第index个节点前面插入一个节点
  • 删除链表的第index个节点

链表操作的两种方式：

  1. 直接使用原来的链表来进行操作。
  2. 设置一个虚拟头结点在进行操作。

下面全篇都是默认有一个虚拟头节点的方式。

如果对头节点操作，头节点的值都被修改了，最后就无法返回头节点。

//全篇都是默认有一个虚拟头节点的方式

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


MyLinkedList* myLinkedListCreate() {
    //设置虚拟头结点的惯用操作
    MyLinkedList *head;
    head=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    head->next=NULL;
    return head;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    int cnt=-1;//使用了虚拟头节点。所以cnt从-1计算。相当于虚拟头节点的下标是-1
    while(obj!=NULL)//遍历obj开始寻找
    {
        if(cnt==index)//找到了下标index的对象
        {
            return obj->val;//返回链表中第 index 个节点的值
            break;//并且跳出
        }
        else 
        {
            cnt++;//否则就下标+1
            obj=obj->next;//obj指向下一个
        }
    }
    return -1;//没找到，循环退出了，就返回-1
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList *tmp;
    tmp=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    tmp->val=val;
    tmp->next=obj->next;//注意使用的是虚拟头节点，所以tmp->next=obj->next
    obj->next=tmp;
    
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    while(obj->next != NULL){
        obj = obj->next;//循环，直到最后一个
    }
    MyLinkedList *tmp;
    tmp=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    tmp->val=val;
    tmp->next=NULL;
    obj->next=tmp;//把tmp直接插在最后
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    int cnt=0;
    MyLinkedList *tmp;
    tmp=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    MyLinkedList *cur;
    cur=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    if(index==0)//index为1就是再头部插入节点
    {
        myLinkedListAddAtHead(obj,val);
        return;
    }
    while(obj!=NULL)
    {
        if(cnt==index)//找到了下标index的对象的前一个对象。开始插入
        {
            tmp->val=val;
            tmp->next=obj->next;
            obj->next=tmp;
            return;//并且跳出
        }
        else
        {
            obj=obj->next;
            cnt++;//否则就下标+1
        }
    }   
    return;

}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    int cnt=0;
    MyLinkedList *tmp;
    tmp=(MyLinkedList *)malloc(sizeof(MyLinkedList));
    if(index==0)
    {
        tmp=obj->next;
        if(tmp!=NULL)
        {
            obj->next=tmp->next;
            free(tmp);
        }
        return;
    }
    while(obj!=NULL)
    {
        if(cnt==index)//找到了下标index的对象
        {
            tmp=obj->next;
            if(tmp!=NULL)
            {
                obj->next=tmp->next;
                free(tmp);
            }
            break;//并且跳出
        }
        else 
        {
            cnt++;//否则就下标+1
            obj=obj->next;
        }
        
    } 
    return;  

}

void myLinkedListFree(MyLinkedList* obj) {
    //释放虚拟头节点
    while(obj!=NULL)
    {
        MyLinkedList *tmp=obj;
        obj=obj->next;
        free(tmp);
    }

}

206.反转链表

1. 题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

2.分析

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:

img

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。最后定义一个临时指针tmp来保存cur->next

以遍历cur为循环，两步操作：

  1. 翻转链表方向

​ 2.全部后移

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    //首先定义一个cur指针,指向头节点
    struct ListNode *cur=head;
    //再定义一个pre，初始化为null
    struct ListNode *pre=NULL;
    //定义一个临时指针tmp来保存cur->next
    struct ListNode *tmp;

    while(cur!=NULL)
    {
        tmp=cur->next;//保留住cur->next
        //1. 翻转链表方向
        cur->next=pre;
        //2.全部后移
        pre=cur;//pre向后移
        cur=tmp;//cur也向后移
    }
    return pre;
}

原文地址：http://www.cnblogs.com/MLcaigou/p/16800985.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性