目录
- 移除链表元素
- 链表的中间节点
- 链表中倒数第K个节点
- 合并两个有序链表
移除链表元素
链接: 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;
}
