● 203.移除链表元素
算法思想：
使用虚拟头结点进行槽位。当涉及到对链表的修改：增加、删除、交换时，需要使用虚拟头结点。
思路：比较判断该节点是否需要删除，需要有一个指针cur指向删除节点的前一个节点，才能对它进行操作，需要比较的是cur->next的值和val。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* father = new ListNode(0);
father->next = head;
ListNode* cur = father;
while(cur->next!=NULL)
{
if(cur->next->val==val)
{
cur->next = cur->next->next;
}
else{
cur = cur->next;
}
}
return father->next;
}
};
● 707.设计链表
算法思想：插入删除的操作时，注意虚拟头节点的使用。
思路：
1.index注意是类似于数组的下标。要在index的位置插入或者删除一个节点，需要找到它的前一个节点。如果把握不好临界条件，可以假设只有1个节点的时候，临界条件是什么。比如index=1，那要找到index=0的节点位置。cur指向虚拟头结点，如果是for(int i=0;i<index;i++) 就发现，循环结束时，正好cur指向前一个节点，满足条件。
class MyLinkedList {
public:
struct ListNode{
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
MyLinkedList() {
size = 0;
head = NULL;
}
ListNode* gethead()
{
return head;
}
int get(int index) {
if(index>=size||index<0)
{
return -1;
}
ListNode* cur = head;
for(int i=0;i<index;i++)
{
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
ListNode *father = new ListNode(val);
father->next = head;
head = father;
size++;
}
void addAtTail(int val) {
ListNode *father = new ListNode(0);
father->next = head;
ListNode* cur = father;
while(cur->next!=NULL)
{
cur = cur->next;
}
cur->next = new ListNode(val);
head = father->next;
size++;
}
void addAtIndex(int index, int val) {
if(index<=size)
{
ListNode *father = new ListNode(0);
father->next = head;
ListNode *cur = father;
for(int i=0;i<index;i++)
{
cur = cur->next;
}
ListNode *innode = new ListNode(val);
innode->next = cur->next;
cur->next = innode;
size++;
head = father->next;
}
}
void deleteAtIndex(int index) {
if(index<size)
{
ListNode *father = new ListNode(0);
father->next = head;
ListNode *cur = father;
for(int i=0;i<index;i++)
{
cur = cur->next;
}
cur->next = cur->next->next;
size--;
head = father->next;
}
}
void printList()
{
ListNode *cur = head;
cout<<"size:"<<size<<endl;
for(int i=0;i<size;i++)
{
cout<<cur->val<<endl;
cur = cur->next;
}
}
private:
int size;
ListNode *head;
};
● 206.反转链表
算法思想：
链表双指针的操作
思路：
用前后两个指针pre和cur进行操作，cur指向要反转的节点，pre指向上一个节点，同时用tmp记录cur的下一个节点。
关键在于循环终止条件是什么：可以设想当cur位于最后一个元素的时候，需不需要继续执行操作，如果需要则在非空的位置停止。
注意区别：
反转链表的时候cur指向的是要改变方向的那个节点，交换两个节点位置的时候，只要的是操作的2节点的前一个节点。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur!=NULL)
{
ListNode* tmp = cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
