经典九道链表OJ题（附详细图解及代码）

前言

众所周知，链表是数据结构里面较为重要的。在我们学完链表的时候当然要练练题试试身手，顺便巩固一下知识。话不多说，直接上题~

一.反转链表（难度：简单）力扣.206

思路：结点头插（运用双指针），例如在结点1处依次头插2 3 4 5

图解

此题比较简单，代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;//用next标记
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

二.链表中倒数第k个结点（难度：简单）牛客

思路：用快慢指针，快的先向前走k步，然后快慢同时走，保证两个指针间隔k
这里需要注意的是一些极端情况，例如链表只有5个结点，要输出倒数第6或者更大的结点，这样就直接返回NULL了。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{// write code here
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;
    while(k--)
    {
        if(fast)
            fast = fast->next;
        else//考虑假如链表5个数要求倒数第6个结点情况
            return NULL;
    }
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

三.合并两个有序链表(难度：简单) 力扣.21

思路：新建一个空链表，拿链表1的头开始依次和链表2比大小尾插到新链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1 == NULL)
    return list2;
    else if(list2 == NULL)
    return list1;//防止两个链表为空
    struct ListNode *head=NULL;    //创空链表
    struct ListNode *tail=NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
    tail->next = NULL;
    while(list1 && list2)
    {//依次比大小进行头插
        if(list1->val < list2->val)
        {
            tail->next=list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next=list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
        if(list1)//剩下list1直接把剩下的list1一起插入
            tail->next = list1;
        else
            tail->next = list2;
 
        struct ListNode* list = head->next;
        free(head);
        return list;
}

四.移除链表元素(难度：简单) 力扣.203

思路：从头节点开始进行元素删除，每删除一个元素，需要重新链接节点
注意：这里要考虑空链表的情况。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val)
{//双指针
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    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;
}

好了下面要开始上点难度了，铁汁们 坚持就是胜利！！！