链表OJ练习（1）-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表OJ练习（1）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、移除链表元素

本题为力扣原题203

题目介绍：

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

链表OJ练习（1）,链表,算法,数据结构,c语言

列表中的节点数目范围在 0~10000内

1<=Node.val<=50

0<=val<=50

思路：利用双指针解决，struct ListNode*dst=NULL;struct ListNode*cur=head;利用指针cur便利整个链表。

注：需要考虑到要删除的是否是头节点。

让我们看看如何来实现：

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


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode*dst=NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            //找到了，删除
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                dst->next=cur->next;
                free(cur);
                cur=dst->next;
            }
        }
        else 
        {
            dst=cur;
            cur=cur->next;
        }
    }
    return head;
}

二、反转链表

本题为力扣原题206

题目介绍：

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

链表OJ练习（1）,链表,算法,数据结构,c语言

思路：利用三指针解决，指针n1和n2用来交换指向，至真n3用来找到下一个节点。

注：需要注意的是判断指针在什么情况下为空，避免利用空指针。n1最开始为空。

让我们看看如何来实现：

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


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

三、链表的中间节点

本题为力扣原题876

题目介绍：

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点

链表OJ练习（1）,链表,算法,数据结构,c语言

思路：快慢指针，快指针每次走两步，慢指针每次走一步，当快指针到达尾部时，慢指针刚好到达中间节点

让我们看看如何来实现：

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

//快慢指针
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* falst;
    struct ListNode* slow;
    falst=head;
    slow=head;
    while(falst&&falst->next)
    {
        slow=slow->next;
        falst=falst->next->next;
    }
    return slow;
}

四、返回倒数第k个节点

题目介绍;

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

链表OJ练习（1）,链表,算法,数据结构,c语言

思路：和上面一题很相似，还是用快慢指针，只不过这次是让，快慢指针都开始指向头节点，让快指针先走k步，然后慢指针和快指针在同时往后走，当快指针到达尾的时候，慢指针就指向了倒数第k个元素了。

注：这里需要注意的是k的大小，当k大于链表长度是就会溢出，这里我们直接返回NULL。

让我们看看如何来实现：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) 
{
    if(pHead==NULL)
    {
        return NULL;
    }
    struct ListNode*slow=pHead;
    struct ListNode*falst=pHead;
    int len=0;
    while(pHead)
    {
        len++;
        pHead=pHead->next;
    }
    if(k>len)
    {
        return NULL;
    }
    while(k)
    {
        falst=falst->next;
        k--;
    }
    while(falst)
    {
        falst=falst->next;
        slow=slow->next;
    }
    return slow;
}

五、合并两个有序链表

题目介绍：

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

链表OJ练习（1）,链表,算法,数据结构,c语言

思路：首先先考虑特殊情况，当链表一为空是返回链表二，链表二为空时返回链表一。然后我们开始遍历链表一和链表二，比较两个指针指向链表的元素大小，创建一个新链表头节点，将小的元素的节点尾插到新链表上，然后将较小元素的指针后移，然后在比较......如果最后链表一遍历完了，就可以将指向链表二的指针指向新链表的尾部，最后然会新链表的头节点。

注：题目时不带头节点的，所以我们创建玩心链表的头节点需要销毁，头指针指向头节点的下一个节点。文章来源地址https://www.toymoban.com/news/detail-689219.html

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

        }
        else
        {
            tail->next=list2;
            tail=tail->next;
            list2=list2->next;

        }   
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    struct ListNode* del=head;
    head=head->next;
    free(del);
    return head;
}

到了这里，关于链表OJ练习（1）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！