LeetCode 203.移除链表元素
题目：给你一个链表的头节点 head 和一个整数val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
代码：
法一：直接对原链表操作。这种方法要考虑两种情况：1、头节点刚好是要删除的点；2、非头节点是要删除的点。第一种情况通过head=head->next实现头节点的移动，第二种情况就是正常的删除节点的操作。有一种特殊情况需要考虑到：例如删除的元素是1，但是链表里面全是1，这时候头节点应该不断地向后移动，直至为空，所以第一种情况的代码中应该用while而不是if。此外在写代码时要注意，我们不能对空指针进行操作，所以在对进入循环时要判断空节点的情况。
/**
* 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!=NULL&&head->val==val)
{
ListNode* temp=head;
head=head->next;
delete temp;
}
ListNode* p=head;
while(p!=NULL&&p->next!=NULL)
{
if(p->next->val==val)
{
ListNode* temp=p->next;
p->next=temp->next;
delete temp;
}
else{
p=p->next;
}
}
return head;
}
};
法二：构造虚拟头节点。这种方法是在头节点之前再加上一个节点，把头节点变成一个中间的节点，避免了法一的分类判断，这样代码更加简洁。需要注意的是，最后返回的指针是vhead->next，因为原来的head可能被删除了，而虚拟头节点的下一个节点永远都是原链表的头节点。
/**
* 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) {
ListNode *vhead=new ListNode(0);
vhead->next=head;
ListNode *p=vhead;
while(p!=NULL&&p->next!=NULL)
{
if(p->next->val==val)
{
ListNode* temp=p->next;
p->next=temp->next;
delete temp;
}else{
p=p->next;
}
}
return vhead->next;
}
};
LeetCode 707.设计链表
题目：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。
代码：
class MyLinkedList {
public:
struct LinkNode{
int val;
LinkNode* next;
LinkNode(int val):val(val),next(NULL){}
};
MyLinkedList() {
vhead=new LinkNode(0);
size=0;
}
int get(int index) {
if (index > (size - 1) || index < 0) {
return -1;
}
LinkNode* cur =vhead->next;
while(index--){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkNode* p=new LinkNode(val);
p->next=vhead->next;
vhead->next=p;
size++;
}
void addAtTail(int val) {
LinkNode* last=new LinkNode(val);
LinkNode* p=vhead;
while(p->next!=NULL)
{
p=p->next;
}
p->next=last;
size++;
}
void addAtIndex(int index, int val) {
if(index>size) return ;
if(index<0) index=0;
LinkNode *newnode=new LinkNode(val);
LinkNode* p=vhead;
while(index--)
{
p=p->next;
}
newnode->next=p->next;
p->next=newnode;
size++;
}
void deleteAtIndex(int index) {
if(index>=size||index<0)
{
return ;
}
LinkNode* p=vhead;
LinkNode* temp=p;
while(index)
{
p=p->next;
index--;
}
temp=p->next;
p->next=temp->next;
delete temp;
size--;
}
private:
int size;
LinkNode *vhead;
};
/**
* 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);
*/
注意：
1、本题在头节点节点之前加入了虚拟头节点vhead，这样在链表中任意一处的添加或者删除操作都能够保持一致性，代码逻辑也更加简介。
2、在删除、添加的时候，因为单链表无法找到前面节点的特性，所以每个要操作的位置是p->next，也就是需要操作的前一个位置才是p。同时，为了避免出错，可以找一个极端的例子带入，比如index=0时，这样写循环条件时就不容易出错。
LeetCode 206.反转链表
题目：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
代码：
法一：双指针法。定义一组指针，开始时cur指向head，pre指向head的前一个元素，因为反转后原本的head会指向NULL，所以pre最开始指向NULL。之后cur->next会指向pre实现反转，然后pre、cur同时向后移动一位，继续上述操作。注意：因为cur->next=pre时原来cur的下一个节点就断开了，为了保证连续性，所以在cur指向pre之前，应该用一个临时节点存着原来cur的下一个节点。
/**
* 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* reverseList(ListNode* head) {
ListNode* cur=head;
ListNode* temp=head;
ListNode* pre=NULL;
while(cur!=NULL)
{
temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
法二：递归法。这种方法本质和双指针是一样的，只不过将双指针的while函数写成了递归的方式。
/**
* 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* reverse(ListNode* pre,ListNode* cur)
{
if(cur==NULL) return pre;
ListNode* temp=cur->next;
cur->next=pre;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
return reverse(NULL,head);
}
};
