删除链表元素
方法一
我们可以遍历一遍链表，然后将等于val的值的节点删除了，然后在将剩余的链接起来即可。我们就需要两个指针，一个遍历链表另一个记录上一个节点的位置，如果相等就删除链接，等到链表遍历结束，就可以得到新的链表，但是这种放大有一个弊端，就是如果头结点就是val我们无法处理，所以我们需要现将头结点是val的情况处理了，头结点是val，我们只需要头删即可。
代码如下：
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL,*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往下走 prev = cur; cur = cur->next; } } return head; }
方法二
我们可以依旧是遍历原链表，但是我们这一次需要一个新的头，然后与val不相等的我们尾插到新的头中就可以了，这个方法比较省事，直接尾插就可以，但是需要注意新的头为空的情况，为了方便尾插，我们需要一个尾指针来记录尾节点的位置。
代码如下：
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head,*tail=NULL,*newhead=NULL; while(cur) { if(cur->val==val) { //相等就删除 struct ListNode* next = cur->next; free(cur); cur = next; } else { //不相等就尾插 if(newhead==NULL) { //第一次尾插 newhead = tail = cur; cur= cur->next; } else { //正常尾插 tail->next= cur; cur = cur->next; tail = tail->next; } } } //尾差的最有后一个节点的next要置NULL，不然可能会非法访问 if(tail!=NULL) //tail等于空说明链表为空，或者链表中的元素都val tail->next = NULL; return newhead; }
反向链表
方法一
我们定义一个空指针，然后翻转链表的指向，但是直接翻转的话我们会丢失下一个节点，所以我们还需要一个指针来记录下一个节点的位置。
代码如下：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL,*cur = head,*next = NULL; while(cur) { //next指向下一个节点 next = cur->next; //翻转指向 cur->next = newhead; //更新新的头结点 newhead = cur; //更新cur cur = next; } return newhead; }
方法二
头插法，我们遍历原链表，然后把节点都头插到新的头处，即可翻转链表。
代码如下：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL,*cur = head; while(cur) { //保存下一个节点 struct ListNode* next = cur->next; //头插 cur->next = newhead; newhead = cur; cur = next; } return newhead; }
链表的中间结点
这个题使用快慢指针就可以解决。我们让慢指针一次走一步，快指针一次走两步，我们就可以知道当快指针为空时，或者当快指针的next为空时此时的慢指针就是中间节点。
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* slow = head,*fast = head; while(fast&&fast->next) { //慢指针走一步 slow=slow->next; //快指针走两步 fast = fast->next->next; } return slow; }
链表中倒数第k个结点
这个题同样使用快慢指针，我们可以让快指针先走k步，然后两个指针一起走，当快指针为空时，慢指针就是倒数第k个节点，如果先让快指针走k-1步的话，当快指针的next为空时，慢指针就是倒数第k个节点。这两种方法都可以。我们实现走k步的
代码如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast = pListHead,*slow = pListHead; while(k--) { // fast=NULL前K个就为空了(判断k是不是过大，以及链表是不是空链表) if(fast==NULL) return NULL; fast = fast->next; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
合并两个排序列表
这个题我们可以同时遍历两个链表，然后拿小的下来尾插，思想差不多就是这样，我们需要一个头，但是这个头可以是哨兵位，也可以是空，我们这里写两个版本的。
带哨兵位的
代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //如果一个链表为空直接返回另一个链表 if(list1==NULL) return list2; if(list2==NULL) return list1; //创建哨兵位 struct ListNode* newhead = NULL,*tail = NULL; newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); 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==NULL) tail->next = list2; if(list2==NULL) tail->next = list1; //保返回的头 struct ListNode* next = newhead->next; //释放哨兵位 free(newhead); return next; }
不带哨兵位
代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //如果一个链表为空直接返回另一个链表 if(list1==NULL) return list2; if(list2==NULL) return list1; struct ListNode* newhead = NULL,*tail = NULL; while(list1&&list2) { if(list1->val<list2->val) { //判断头结点是否为空 if(newhead==NULL) { newhead = tail = list1; list1 = list1->next; } else { tail->next = list1; tail = tail->next; list1= list1->next; } } else { //判断头结点是否为空 if(newhead==NULL) { newhead = tail = list2; list2 = list2->next; } else { tail->next = list2; tail = tail->next; list2= list2->next; } } } //如果一个链表为空，直接将另一个链表链接过来 if(list1==NULL) tail->next = list2; if(list2==NULL) tail->next = list1; return newhead; }
今天的分享就到这里了，感谢大家的支持和关注。
