力扣203. 移除链表元素
没有难度，只需掌握一个思路，即因为每次删除元素时，我们需要该元素的前一个元素的指针来操作，那么如果删除第一个元素呢？他的前一个元素无法获取因此需要进行特殊处理，而我们可以设置一个虚拟节点作为头结点，这样链表的每个元素的处理方式就统一了。
代码如下
ListNode* removeElements(ListNode* head, int val) {
//设置虚拟头结点
ListNode* dummyHead = new ListNode(0, head);
//遍历的当前节点
ListNode* cur = dummyHead;
while (cur->next)
{
if (cur->next->val == val)
{
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else
{
cur = cur->next;
}
}
return dummyHead->next;
}
力扣707. 设计链表
思路还是一样，利用虚拟头结点统一逻辑处理方式，难点在于太复杂了，边界值不清晰，照着答案都得改半天。
代码如下：
class MyLinkedList {
public:
//定义节点结构体
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
MyLinkedList() {
dummyHead_ = new LinkedNode(0);
size_ = 0;
}
//返回index，此时index从0开始
int get(int index) {
if (index < 0 || index > (size_ - 1))
{
return -1;
}
LinkedNode* cur = dummyHead_->next;
while (index--)
{
cur = cur->next;
}
return cur->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* cur = dummyHead_;
while (cur->next != nullptr)
{
cur = cur->next;
}
cur->next = newNode;
size_++;
}
void addAtIndex(int index, int val) {
if (index < 0 || index > size_)
{
return;
}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = dummyHead_;
while(index--)
{
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size_++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size_)
{
return;
}
LinkedNode* cur = dummyHead_;
while(index--)
{
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
size_--;
}
private:
int size_;
LinkedNode* dummyHead_;
};
/**
* 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. 反转链表
代码
ListNode* reverseList(ListNode* head) {
ListNode* tmp;
ListNode* cur = head;
ListNode* pre = nullptr;
while (cur)
{
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}