💕人生不满百，常怀千岁忧💕

作者：Mylvzi 

 文章主要内容：链表oj详解 

题目一：移除元素

题目要求：

画图分析： 

 

代码实现： 

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;
            cur = cur->next;
        }
    }
    return head;
}

题目二：（快慢指针应用）

题目要求 : 

画图分析：

代码实现：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow = head,*fast = head;

    //开始移动
    while(fast && fast->next)//循环条件
    {
        fast = fast->next->next;//一次移动两步
        slow = slow->next;
    }

    return slow;
}

 题目三：求倒数第K个结点

题目要求：

画图分析：

 代码实现：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*slow = pListHead,*fast = pListHead;

    //先让fast走k步，使相对距离为K
    while(k--)
    {
        //如果fast是NULL,不存在fast->next，所以要单独讨论
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }

    //一起前进，直到fast是尾结点
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

 总结：

快慢指针:
1.相对速度，fast一次走两步，slow一次走一步，fast到终点，slow刚好到中间位置（fast的位置要分奇偶，奇数fast走到韦结点即可，偶数fast走到Null）
2.相对路程，求倒数第k个，先让fast走k步，则fast和slow的相对距离一直是k，fast走到null，slow刚好走到倒数第k个
注意循环条件

题目四：合并两个有序链表

题目要求：

画图分析：

代码实现： 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //如果有一个链表为空，直接返回另一个链表即可
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;

    //创建head和tail，便于进行尾插
    struct ListNode* head = NULL,*tail = NULL;

    //思路：取小的尾插
    while(list1 && list2)//有一个为空就推出
    {
        if(list1->val < list2->val)
        {
            if(tail == NULL)//链表为空，直接复制
            {
                head = tail = list1;
            }
            else//不为空，进行尾插
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            if(tail == NULL)//链表为空，直接复制
            {
                head = tail = list2;
            }
            else//不为空，进行尾插
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }

    //出循环，证明有一个已经遍历完
    if(list1)//list1未遍历完
        tail->next = list1;
    if(list2)//list1未遍历完
        tail->next = list2;

    return head;
}