移除链表元素

链接: link
题目描述：

思路分享：

我们上个博客分享了第一种方法，下面我们分析第二种方法：思路就是将每一个不等于我们要删除的值的节点依次尾插。
我们要记录我们尾插之后的新的头，以便于我们将新链表的头返回。
尾插的情况有以下两种：
如果当前要插入的值不是我们要删除的值时，我们要判断以下两种情况
1.链表没有元素，是空链表，这时就需要我们将链表新的头赋值为当前节点的值，并且此时的尾也指向链表新的头。newhead=tail=cur。
2.链表当中没有元素，不是空链表时，将此节点直接插入到当前链表的尾部。tail->next = cur，tail = tail ->next
如果当前要插入的值是我们要删除的值时：
新定义一个节点用来保存我们要删除的节点，将cur指针指向下一个节点，再free掉我们定义的节点。struct ListNode* del = cur;cur = cur->next ;free(del);
这里要注意两个点：
1.每次进行插入操作之后，cur指针都要向下移动
2.为了避免出现野指针问题，每次进行插入结束后，尾指针的next域都要置空。

这里出现一个问题，cur指针向下移动和tail的next域置空的顺序：

为什么第一个是正确的呢？
解答：
下图步骤意思是：让newhead和tail指针指向节点1

此时cur指向1节点，cur的next依旧指向的是节点2，这一点并没有改变，所以cur=cur->next指向的是节点2。
但是如果先将tail->next置空，那么cur->next也是空，因为此时cur和tail指向的是同一个节点的，所以此时cur->next也是NULL，会导致cur=cur->next时候找不到下一个节点，所以我们的顺序必须是先cur=cur->next，再将tail->next置空。
代码实现：

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while (cur){if (cur->val != val)//和删除的值不相等{if (tail == NULL)//第一次插入{newhead = tail = cur;}else{tail->next = cur;tail = tail->next;}tail->next = NULL;cur = cur->next;}else//和删除的值相等{struct ListNode* del = cur;cur = cur->next;free(del);}}return newhead;
}

链表的中间节点

链接: link
题目描述：

题目思路：

快慢指针slow和fast
slow指针一次走一步，fast指针一次走两步。快指针速度是慢指针二倍，当快指针走到终点时，慢指针正好指向中间节点。
这里存在两种情况：刚好这两种情况可以作为我们循环的判断条件。
1.fast->next=NULL

2.fast=NULL

代码实现：

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;
}

链表中倒数第K个节点

链接: link
题目描述：

题目思路：

本题我们的思路依然是一个快慢指针的问题

fast走到最后一个元素时，slow和fast同时向下一个节点移动，直到fast指向的位置为空，slow指向的位置就是我们要返回的元素。
本题我们要找倒数第1个节点，那么就以第一个节点为例，当slow和fast指针拉开1个举例时，两个指针同时向下移动，直到下面情况，slow指向的就是我们要找的值。

注意两点问题
1.如果链表的长度小于k的时候，也会造成fast空指针问题，所以在fast指针走k次的循环过程中，要保证不是因为单链表长度小于k而造成的空指针问题。
2.同时也要判断传过来的pListHead不为空或者k的值是否小于等于0，只要二者有一个满足，就要返回NULL。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{if (!pListHead || k <= 0)//保证传过来的头不是空并且k的值是有效值{return NULL;}//开始两个指针同时指向链表的头struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;while (k--){if (fast){fast = fast->next;}else{return NULL;//单链表长度小于K会造成fast空指针}}while (fast){slow = slow->next;fast = fast->next;}return slow;
}

合并两个有序链表

链接: link
题目描述：


题目思路：

两个指针同时指向List1和List2两链表头部。开始进行链接：
本题需要5个指针，List1，List2，tail，newhead
1、如果List1的值比List2的值小，那么List1的头就是我们合并后链表新的头，newhead = List1，之后让List1指向下一个节点，并且tail指向刚刚被插入的节点。
与此同时如果List2的值比List1的值小，那么List2的头就是我们合并后链表新的头，newhead = List2，之后让List2指向下一个节点，并且tail指向刚刚被插入的节点。
2、有了新链表的头之后，剩下的步骤就是比较两个节点的大小，那个节点值大，就将哪个节点拿下来尾插，并且让尾指针tail指向该尾插的节点。
3、在进行不断的尾插的过程中肯定会有一条链表为空，如果是List1为空，那么直接让tail->next链接List2，否则链接List1。
注意：
我们还要注意一点就是，很有可能给我们的两条链表有一条是空链表，此时只需要返回那条不为空的链表就好。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}if(list1==NULL&&list2==NULL){return NULL;}struct ListNode* newhead = NULL;struct ListNode* tail = NULL;while(list1&&list2){if(list1->val<list2->val){if(newhead ==NULL){newhead = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{if(newhead ==NULL){newhead = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if(list1){tail->next = list1;}if(list2){tail->next = list2;}return newhead;
}