大家好呀，今天向大家分享的是关于单链表的一些比较基础且经典的题目，相信你看完了一定会对单链表的知识掌握的更加熟练。
1 移除链表元素
题目描述：
解题思路：
遍历链表，用cur表示当前位置，记录要去除元素的前一位地址（prev），让prev->next=cur->next.然后不断迭代，直至cur为空.
但是要额外处理当第一个元素就是要去除元素这种情况。
具体代码实现：
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur) { if(cur->val == val) { //头删 if(cur == head) { head=cur->next; free(cur); cur=head; } else { prev->next=cur->next; free(cur); cur=prev->next; } } else { prev=cur; cur=cur->next; } } return head; }
结果展示：
2 反转链表
题目描述：
解题思路1：
遍历链表，让cur指向当前位置，记录cur前一位的位置prev,记录cur后一位位置next,让cur->next=prev,将prev=cur,cur=next,next=next->next,然后不断迭代，结束条件是cur为NULL，但是要注意当next为NULL时就不要进行next=next->next。
具体代码：
ListNode* reverseList(struct ListNode* head) { if(head==NULL) { return head; } struct ListNode* prev=NULL; struct ListNode* cur=head; struct ListNode* next=head->next; while(cur) { //翻转 cur->next=prev; prev=cur; cur=next; if(next) { next=next->next; } } return prev; }
结果展示：
解题思路2：
遍历链表，将链表中的元素头插到一个新链表的头上，然后迭代下去，直到cur为NULL，但是要注意保存cur的下一个位置。
具体代码：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) { struct ListNode* next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; }
结果展示：
两种方法都是可行的，具体用哪一种可以自己选择，但是不要刻意去关注leetcode结果展示中的执行用时和内存消耗，这可能与网速有关。
3 链表的中间结点
题目描述：
解题思路：
常规思路：遍历链表求链表长度，然后再遍历一遍数组求中间结点
具体代码：
struct ListNode* middleNode(struct ListNode* head) { int count=0; struct ListNode* cur=head; while(cur) { count++; cur=cur->next; } cur=head; int i=0; for(i=0;i<count/2;i++) { cur=cur->next; } return cur; }
这种方法可行，但是有没有其他方法只遍历一遍链表呢？
快慢指针：让slow一次走一步，fast一次走两步，直到fast或者fast->next为NULL时结束，此时slow就是中间结点。
具体代码：
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
结果展示：
4 链表中倒数第k个结点
题目描述：
解题思路：
仍然用快慢指针解题，让快指针先走k步，然后同时走。
具体代码：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* slow=pListHead; struct ListNode* fast=pListHead; while(k--) { if(!fast) return NULL; fast=fast->next; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }
其中值得注意的是当fast先走时并且当fast为空时直接返回NULL。
结果展示：
5 合并两个有序链表
题目描述：
解题思路1：
不创建头结点，一 一遍历两个链表，将较小的值拿下来尾插，然后迭代下去，直至其中一个链表为空，然后把另外一个链表剩下的结点全部链接。但是要注意考虑头为NULL的特殊情况。
具体代码：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head=NULL; struct ListNode* tail=NULL; if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } while(list1 && list2) { if(list1->val < list2->val) { if(head==NULL) { tail=head=list1; } else { tail->next=list1; tail=tail->next; } list1=list1->next; } else { if(head==NULL) { tail=head=list2; } else { tail->next=list2; tail=tail->next; } list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } return head; }
结果展示：
解题思路2：
创建一个头结点，不存储数据，方法与第一种类似，但是不需要考虑头为NULL的情况。
具体代码：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail=head; while(list1 && list2) { if(list1->val < list2->val) { tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } struct ListNode* first=head->next; free(head); return first; }
结果展示：
6 链表分割
题目描述：
解题思路：
创建两个头结点分别连接<x和>=x的链表，最后将较小链表的尾连接到大链表的头的下一位，最后别忘了给大链表的尾置NULL。
具体代码：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode*headSmall=(ListNode*)malloc(sizeof(ListNode)); ListNode*tailSmall=headSmall; ListNode*headBig=(ListNode*)malloc(sizeof(ListNode)); ListNode*tailBig=headBig; ListNode*cur=pHead; while(cur) { if(cur->val < x) { tailSmall->next=cur; tailSmall=cur; } else { tailBig->next=cur; tailBig=cur; } cur=cur->next; } tailSmall->next=headBig->next; tailBig->next=NULL; return headSmall->next; } };
结果展示：
