数据结构 --链表题目

1.删除链表中等于给定值val的所有节点

代码示例（C语言）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prve = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val == val)
        {
            struct ListNode* tem = cur->next;
            if(cur == head)
                head = tem;
            else
                prve->next = tem;
            free(cur);
            cur = tem;
        }
        else
        {
            prve = cur;
            cur = prve->next;
        }
    }
    return head;
}

2.反转一个单链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

来源：力扣（LeetCode）
链接：

代码示例（C语言）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
        return NULL;
    if(head->next == NULL)
        return head;
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    while(n3)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        n3 = n3->next;
    }
    n2->next = n1;
    return n2;

}

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

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

来源：力扣（LeetCode）
链接：

代码示例（C语言）:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    //通过两个指针找到
    struct ListNode *fast = head, *slow = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

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

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

来源：牛客
链接：

代码示例（C语言）：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead == NULL)
        return NULL;
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;
    while(fast)
    {
        if(k)
        {
            fast = fast->next;
            k--;
        }
        else
        {
            fast = fast->next;
            slow = slow->next;
        }
    }
    if(k!=0)
    {
        return NULL;
    }
    else
    {
        return slow;
    }
}