[数据结构与算法]单链表的OJ题。

力扣203---- 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解题思路：
1首先呢，我们需要判断特殊的3种情况.

2，这里为了解题方便，我们可以采用带哨兵位的头节点，我画一下示意图

来，看代码

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* newhead,*tail;
    tail=newhead=(struct ListNode*)malloc(sizeof(struct ListNode));  //创建1个节点，用tail和newhead指向
    while(head)
    {
        if(head->val==val)   //如果head等于val，就向后走一下
        {
            head=head->next;
        } 
        else
        {
           tail->next=head;    //如果不相等，就连接一下
           tail=tail->next;
           head=head->next;
        }
    }
    tail->next=NULL;      //这里防止的是head最后一个元素等于val，所以要手动置空。
    return newhead->next;
}

力扣206—反转单链表

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
题目用途描述就是：

解题思路：
采用前后指针的方法，这里尽量不要用递归的方法，因为万一节点数比较多，就一定存在着溢出的情况
看图理解：

看代码

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* pre=NULL,*cur=head;   //pre一定要置空
    while(cur)
    {
        struct ListNode* save=cur->next;    //保存一下cur的下一个节点，不然找不到啦
        cur->next=pre;
        pre=cur;
        cur=save;
    }
    return pre;
}

力扣876—链表的中间节点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

解题思路：
使用快慢指针，快指针走2步，慢指针走1步,快指针为空时,慢指针就是中间节点
但是要考虑奇数个和偶数个节点两种情况,
如果是偶数个节点,fast不为空就可以
如果是奇数个节点,fast->next不为空

看代码

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow=head,*fast=head;
    while(fast && fast->next)    //这里循环条件的判断一定不能颠倒,否则会报错,因为fast->next不为空,fast一定不为空
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

牛客网----链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

解题思路:
使用快慢指针的方法,快指针先走k步,然后让快,慢指针一起走,快指针为空的时候,慢指针即为所求
注意一下: 如果k为0呢? 如果`k大于链表的长度呢?

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
    struct ListNode*  fast=pListHead,*slow=pListHead;
     if(k==0)
         return NULL;
    while(k)      //先让快指针走k步
    {
     k--;
        if(fast==NULL)
        return NULL;
     fast=fast->next;   
    }
    while(fast)     //然后一起走
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
    // write code here
}

力扣21-----合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路:
为了方便,仍旧使用带哨兵位的头节点 ,画图示意一下带和不带的区别

这样就很简单了,两个链表依次比较,小的就向放入目标链表.
最后,如果一个链表为空,连接上另一个不为空的就可以了.

看代码

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

    if(list1)      
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head->next;
}