目录
一：创建和打印链表
?力扣给出的结构体
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) {} };传入一个数组，构建一个链表
- 值得注意的是链表的第一个元素很重要，必须记录
- 传入一个链表头结点，就可以遍历出整个链表
/*创建一个链表*/ ListNode* createList(int a[],int n){ //返回指向链表第一个元素的指针,传入一个数组：数组头指针和数组大小 if(n==0) return 0;//数组无元素 /*创建头指针head，这里是指向第一个元素的*/ ListNode* head=new ListNode(a[0]); /*利用该指针，创建好余下数据*/ ListNode* cur=head; for(int i=1;i<n;i++){ cur->next=new ListNode(a[i]); cur=cur->next; } return head; }由于没有辅助的头结点，类似尾插法，头指针不断在变化，需要格外的引用记录头指针
- cur->next=new ListNode(a[i]);----------将新结点链入
- cur=cur->next;---------头结点在变化
打印一个链表
void printLink(ListNode* head) { ListNode* cur=head; while(cur){ cout<<cur->val<<"->"; cur=cur->next; } cout<<"null"<<endl; }
二：反转链表?
链表问题中：一般要求对指针进行操作，而不是链表的值
?分析：
? ? ? ? ? ?因为要实现把该结点指针指向其前驱，所以一个指针记录当前结点cur，一个记录cur前一个结点pre.但是这个时候cur没法沿着链条向前移动了，断链了。所以cur的后继suc也需要记录，保证了cur和pre的正常前移。
模拟
- 把cur的next指针指向pre，完成单个反转
- 然后pre指向cur，cur指向suc，suc前移
ListNode* reverseList(ListNode* head) { ListNode* pre=NULL; ListNode* cur=head;//从第一个结点开始 while(cur){//不定义suc=head->next,防止不存在造成泄漏 ListNode* suc=cur->next;//保证了链不断 /*反转*/ cur->next=pre; /*更新*/ pre=cur; cur=suc; //suc=suc->next;没有这句话 } return pre;//pre在结束时，指向了链表的第一个元素 }法二：不把suc视为cur的存在而存在
ListNode* reverseList(ListNode* head) { ListNode* pre=NULL; ListNode* cur=head;//从第一个结点开始 if(cur==NULL||cur->next==NULL) return cur; ListNode* suc=head->next; while(cur){ /*反转*/ cur->next=pre; /*更新*/ pre=cur; cur=suc; if(suc) suc=suc->next; } return pre;//pre在结束时，指向了链表的第一个元素 }这时候比较需要注意就是：没有NULL->next
所以每次更新suc需要判断一下自己是否为空，把suc不存在的情况:cur->next或cur为空的情况提前return
?自己的测试台程序测试：
#include<iostream>
using namespace std;
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) {}
};
/*创建一个链表*/
ListNode* createList(int a[],int n){
//返回指向链表第一个元素的指针,传入一个数组：数组头指针和数组大小
if(n==0) return 0;//数组无元素
/*创建头指针head，这里是指向第一个元素的*/
ListNode* head=new ListNode(a[0]);
/*利用该指针，创建好余下数据*/
ListNode* cur=head;
for(int i=1;i<n;i++){
cur->next=new ListNode(a[i]);
cur=cur->next;
}
return head;
}
/*打印一个链表*/
void printLink(ListNode* head) {
ListNode* cur=head;
while(cur){
cout<<cur->val<<"->";
cur=cur->next;
}
cout<<"null"<<endl;
}
/*为防止内存泄漏，释放节点*/
void deleteNode(ListNode* head){
ListNode* cur=head;
while(cur){//当前指向结点不为空
ListNode* delNode=cur;
cur=cur->next;//沿着链表移动
delete delNode;
}
}
/*反转一个链表*/
ListNode* revList(ListNode* head){
ListNode* pre=NULL;
ListNode* cur=head;
while(cur){
ListNode* suc=cur->next;
//操作
cur->next=pre;
//更新
pre=cur;
cur=suc;
}
return pre;
}
int main(){
int a[]={9,2,44,57,67,123};
int n=sizeof(a)/sizeof(int);
ListNode* head=createList(a,n);
printLink(head);
ListNode* head2=revList(head);
printLink(head2);
deleteNode(head2);
}三：删除重复的链表?
?本题要求删除所有重复元素：
首先建立一个查找表，该查找表只添加不删除
然后：每遇到一个元素从查找表找，分为查到和没查到两种可能。
删除一个结点需要用到前驱pre，这里cur的next指针不变，不必设立后继
- 没查到-----查找表添加该元素，pre指向cur,cur指向下一个
- 查到了-----新建delNode指向cur以便delete,pre不动，改变next；cur指向下一个
ListNode* deleteDuplicates(ListNode* head) { ListNode* pre=NULL; ListNode* cur=head; set<int> record; while(cur){ if(record.find(cur->val)==record.end()){ record.insert(cur->val); pre=cur; cur=cur->next; } else{ ListNode* delNode=cur; pre->next=cur->next; cur=cur->next; delete delNode; } } return head; }return的是head,因为从头遍历
四：删除链表的元素?
法一：
ListNode* removeElements(ListNode* head, int val) { /* 因为头结点元素的delete改变了头指针head,其他位置head可遍历链 故而：要考虑待删的是不是头结点 又因为：可能多个重复值，所以用while */ while(head && head->val==val){ ListNode* delNode=head; head=head->next;//这句话的前提是head不为空 delete delNode; } if(head==NULL) return head; /*删除需要前驱*/ ListNode* pre=head; ListNode* cur=head->next; while(cur){ if(cur->val==val){ ListNode* delNode=cur; pre->next=cur->next; cur=cur->next; delete delNode; } else{ pre=cur; cur=cur->next; } } return head; }注意几个细节：
首先删除头结点就是待删元素是，为了避免多次出现用while
比如：3->3->3->4->5->6->6,删除元素3,得多次
其次由于cur指向了head->next,为了避免NULL->next,必须if判断。
最后：元素是待删元素，元素不是待删元素两种情况，必须if-else
这里可以不使用前驱pre
ListNode* removeElements(ListNode* head, int val) { while(head && head->val==val){ ListNode* delNode=head; head=head->next;//这句话的前提是head不为空 delete delNode; } if(head==NULL) return head; //判断当前元素下一个元素，自己作为前驱 ListNode* cur=head; while(cur->next){ if(cur->next->val==val){ ListNode* delNode=cur->next; cur->next=delNode->next; delete delNode; } else{ cur=cur->next; } } return head; }法二：设立虚拟头结点
ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead=new ListNode(0);//虚拟头结点 dummyHead->next=head;//虚拟头结点指向真正的head ListNode* cur=dummyHead; while(cur->next){ if(cur->next->val==val){ ListNode* delNode=cur->next; cur->next=delNode->next; delete delNode; } else{ cur=cur->next; } } ListNode* retHead=dummyHead->next; delete dummyHead; return retHead;//真正返回的是虚拟头结点前一个 }很简单，创建一个头结点，让其next指向真正的头结点head
然后两种情况合二为一，因为如果将虚拟结点视为头结点，删除元素一定属于第二种
最后返回该节点的next指针即可，但是因为要delete,记录一下。
以链表?1->2->3-null?为例子，删除值为 3 的节点?
?
?
?
?
?
?
?
?
首先看一下下面的程序：
LinkNode* simpleRec(LinkNode* head) { if(head==NULL) return head;//递归结束条件 LinkNode* pre; pre=removeElements(head->next); head->next=pre;//把结点链入 //test---pre的值 if(pre) cout<<"pre is "<<pre->val<<endl; else cout<<"pre is null"<<endl; printLink(head);//测试当前链 cout<<endl; return head; }运行结果：
?发现还是递归的思想
每次因为pre，把链表不断通过head=head-<next形成子链，然后执行head==NULL后，程序开始向上回调，pre指向的子链：逐渐从NULL倒着向前增长，这时候结合题干，就可以达到目的。
ListNode* removeElements(ListNode* head, int val) { //递归结束条件 if(head==NULL) return NULL; //递归子链 ListNode* res=removeElements(head->next,val); //对结果进行选择 if(head->val==val){ //不要head,取子链 return res; } else{ //要head,链入子链 head->next=res; return head; } }?进一步简化
ListNode* removeElements(ListNode* head, int val) { //递归结束条件 if(head==NULL) return head; //递归子链 head->next=removeElements(head->next,val); //对结果进行选择 return head->val==val?head->next:head; }把res这个变量直接作为：head->next的子链
可以把这个递归思路沿用到--删除重复元素
ListNode* deleteDuplicates(ListNode* head) { if(head==NULL) return head; set<int> record; head->next=deleteDuplicates(head->next); if(head->next) record.insert(head->next->val); if(record.find(head->val)==record.end()){ return head; } else{ return head->next; } }
五： 两两交换链表节点?
复杂的穿针引线： Swap Nodes in Pairs 其实不难：
关键要分析好需要那些节点指针
既然要交换肯定需要指向两个节点指针：node1和node2
而且为了成链，需要知道待交换的两个结点的前一个指针p和后一个指针q.
为了避免头结点的情况讨论，设立虚拟头结点dummyHead
?最后更新一下p的位置即可
ListNode* swapPairs(ListNode* head) { //创建虚拟头结点 ListNode* dummyHead=new ListNode(0); dummyHead->next=head; ListNode* p=dummyHead; /*交换的前提，两个结点均存在*/ while(p->next&&p->next->next){ //定义两个结点+后继 ListNode* node1=p->next; ListNode* node2=p->next->next; ListNode* q=node2->next; //交换节点 node2->next=node1; node1->next=q; p->next=node2; //更新 p=node1;//细节---交换后，node1指向了较后面的结点 } //返回结果，释放头结点 ListNode* res=dummyHead->next; delete dummyHead; return res; }
?六：删除结点
不仅仅是穿针引线?
?
?void?deleteNode(ListNode*?node) {}
void deleteNode(ListNode* node) { if(node==NULL) return; if(node->next==NULL){ delete node; node=NULL; return; } node->val=node->next->val; ListNode* delNode=node->next; node->next=delNode->next; delete delNode; }把待删结点用其后一个结点赋值，删除后一个结点即可
这里是改变链表的某一个值来达到目的
七：删除链表倒数第n个结点
?只遍历一遍链表，不从链表长度入手
思路：
因为要删第n个，需要找到它的前一个结点。不妨让指针p，q之间距离为n+1.
p从头遍历，p,q每次都移动一步（相同距离），最后q==NULL,p就恰好指向待删结点前驱
?
?
ListNode* removeNthFromEnd(ListNode* head, int n) { assert(n>=0); ListNode* dummyHead=new ListNode(0); dummyHead->next=head; //定义双指针 ListNode* p=dummyHead; ListNode* q=dummyHead; //设定p,q距离为n+1 for(int i=0;i<n+1;i++){ assert(q); q=q->next; } while(q){ p=p->next; q=q->next; } //删除 ListNode* delNode=p->next; p->next=delNode->next; delete delNode; //返回 ListNode* res=dummyHead->next; delete dummyHead; return res; }
