203. 移除链表元素
/**
* 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* removeElements(ListNode* head, int val)
{
while (head != nullptr && head->val == val)
{
head = head->next;
}
ListNode* node = head;
while (node != nullptr && node->next != nullptr)
{
if (node->next->val == val)
{
node->next = node->next->next;
}
else
{
node = node->next;
}
}
return head;
}
};
707. 设计链表
class MyLinkedList {
public:
struct linknode
{
int val;
linknode* next;
linknode(int x): val(x), next(NULL){}
};
MyLinkedList()
{
this->head = new linknode(0);
this->size = 0;
}
int get(int index)
{
linknode* cur = this->head;
if (this->size == 0) return -1;
else if (index > this->size-1) return -1;
else
{
for (int i=0; i<index; i++)
{
cur = cur->next;
}
}
return cur->val;
}
void addAtHead(int val)
{
if (this->size == 0)
{
this->head->val = val;
this->size = 1;
}
else
{
linknode* cur = new linknode(val);
linknode* tmp = this->head;
this->head = cur;
cur->next = tmp;
this->size += 1;
}
}
void addAtTail(int val)
{
if (this->size == 0)
{
this->head->val = val;
this->size = 1;
}
else
{
linknode* cur = new linknode(val);
linknode* tmp = this->head;
while (tmp->next != NULL)
{
tmp = tmp->next;
}
tmp->next = cur;
this->size++;
}
}
void addAtIndex(int index, int val)
{
if (index > this->size) return;
else if (index == this->size) addAtTail(val);
else if (index == 0) addAtHead(val);
else
{
linknode* cur = this->head;
linknode* newnode = new linknode(val);
for (int i=0; i<index-1; i++)
{
cur = cur->next;
}
linknode* tmp = cur->next;
cur->next = newnode;
newnode->next = tmp;
this->size++;
}
}
void deleteAtIndex(int index)
{
if (this->size == 0) return;
else if (index > this->size-1) return;
else{
if (index == 0) this->head = this->head->next;
else if (index == this->size-1)
{
linknode* cur = this->head;
while (cur != NULL && cur->next != NULL && cur->next->next != NULL)
{
cur = cur->next;
}
cur->next = NULL;
}
else
{
linknode* cur = this->head;
for (int i=0; i<index-1; i++)
{
cur = cur->next;
}
cur->next = cur->next->next;
}
this->size--;
}
}
private:
linknode *head;
int size;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
206. 反转链表
自己写的是从后往前去反转,没想到可以从前往后反转的方法,以为地址不连续并且无法根据索引找地址就没办法做,看了双指针方法后才发现如何从前往后反转,其实只要记录每个结点的地址就可以了,还是对链表的概念把握的不好,需要多刷题。
自己做的:文章来源:https://www.toymoban.com/news/detail-826335.html
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
if (head==nullptr) return head;
if (head->next==nullptr) return head;
ListNode* newnode = head;
ListNode* tmp1 = head;
// while (newnode != nullptr && newnode->next != nullptr && newnode->next->next != nullptr)
// {
// newnode = newnode->next;
// }
// ListNode*
int flag = 0;
while (head->next != nullptr)
{
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr && cur->next->next != nullptr)
{
cur = cur->next;
}
if (flag == 0)
{
newnode = cur->next;
tmp1 = cur->next;
cur->next = nullptr;
}
else
{
ListNode* tmp = cur->next;
cur->next = nullptr;
tmp1->next = tmp;
tmp1 = tmp;
}
flag++;
}
tmp1->next = head;
return newnode;
}
};
双指针:文章来源地址https://www.toymoban.com/news/detail-826335.html
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点,因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};
到了这里,关于代码随想录-链表1( 203.移除链表元素、)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!