203.移除链表元素
1. 题目
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：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个节点
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
下面全篇都是默认有一个虚拟头节点的方式。
如果对头节点操作，头节点的值都被修改了，最后就无法返回头节点。
//全篇都是默认有一个虚拟头节点的方式
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：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
2.分析
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。最后定义一个临时指针tmp来保存cur->next
以遍历cur为循环，两步操作：
- 翻转链表方向
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;
}