移除链表元素
leetcode
删除链表中等于给定值 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 输出:[]
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode * hummyhead = new ListNode(0);
hummyhead -> next = head;
ListNode *current = hummyhead;
while ( current -> next != NULL ) {
if( current -> next -> val == val ) {
ListNode * dele = current -> next ;
current -> next = current -> next ->next ;
delete dele;
}
else current = current -> next ;
}
return hummyhead -> next;
}
};
移除元素 主要是 找到要移除的前一个 , 之后才能移除 。采用虚拟头节点的方法 ,用current 记录比较元素的 前一个 ,如果找到元素 那current 就是前一个 ,注意 循环结束条件 。
设计链表
leetcode
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode *next;
LinkedNode ( int val ) : val(val), next(nullptr){}
};
MyLinkedList() {
dummyhead = new LinkedNode(0);
size = 0;
}
int get(int index) { // 获得指定位置的值
if ( index < 0 || index >= size) {
return -1;
}
LinkedNode *current = dummyhead -> next;
while ( index-- ) {
current = current -> next;
}
return current -> val;
}
void addAtHead(int val) { // 在链表头添加节点
LinkedNode *newnode = new LinkedNode(val);
newnode -> next = dummyhead -> next;
dummyhead -> next = newnode;
size++;
}
void addAtTail(int val) { //在尾部插入结点
LinkedNode *newnode = new LinkedNode(val);
LinkedNode *current = dummyhead;
while ( current -> next != nullptr ) {
current = current-> next;
}
current -> next = newnode;
size++;
}
void addAtIndex(int index, int val) { //在下表为index 处插入节点
if ( index < 0 ) index = 0;
if ( index > size )return ;
LinkedNode *newnode = new LinkedNode(val);
LinkedNode *current = dummyhead;
while (index--) {
current = current -> next;
}
newnode -> next = current -> next;
current -> next = newnode;
size++;
}
void deleteAtIndex(int index) { //删除指定下标节点
if ( index < 0 || index >= size) return;
LinkedNode *current = dummyhead;
while ( index-- ) {
current = current -> next;
}
LinkedNode *tem = current -> next;
current -> next = current -> next -> next;
delete tem;
size--;
}
private:
int size;
LinkedNode * dummyhead;
};
反转链表
leetcode
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
可以采用 双指针 和 递归 , 递归实际是 双指针的 精简
以下是采用递归的代码
class Solution {
public:
ListNode* digui (ListNode* current,ListNode * pre) {
if ( current == nullptr ) return pre;
ListNode* tem = current -> next;
current -> next = pre;
return digui(tem,current);
}
ListNode* reverseList(ListNode* head) {
return digui(head , nullptr);
}
};
以下是采用双指针的代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode * current = head;
ListNode *pre = nullptr;
while ( current != nullptr ) {
ListNode *tem = current -> next;
current -> next = pre;
pre = current;
current = tem;
}
return pre;
}
};
实际上 递归 是 把双指针的 while 简化 , 减少了对current 和 pre 的 重复 赋值文章来源:https://www.toymoban.com/news/detail-477429.html
此题 关键 是要 注意 改变链表之间的连线时 要注意不要和后面的 断掉联系 ,可以用临时指针 保存后面的节点文章来源地址https://www.toymoban.com/news/detail-477429.html
到了这里,关于移除链表元素 , 设计链表 ,反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!