C语言单链表OJ题(较易)

一、移除链表元素

leetcode链接

题目描述:

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

思路:

正常遍历,找到value的值与题目中相同的结点去free掉,分为两种情况:

第一种就是头结点就是value值,直接将头节点指向next;

第二种情况就是第二个结点开始是value,需要有一个前结点指向value结点的下一个。

源码:

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //链表本身为空
    if(head==NULL)
        return NULL;
    struct ListNode* prev = NULL;
    while(1)//头节点开始就是值
    {
        if(head->val==val)
        {
            prev=head;
            head=head->next;
            free(prev);
            if(head==NULL)
            {
                return NULL;
            }
        }
        else
        {
            break;
        }
    }
    struct ListNode* cur = head;
    while(cur)//从第二个开始才是value,可以使用prev,因为第一个不是value,可以存储
    {
        //这一部分卡了好久
        if(cur->val==val)
        {
            prev->next=cur->next;    
            struct ListNode* del=cur;
            free(del);
            cur=prev->next;
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

二、链表的中间结点

leetcode链接

题目描述:

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

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

思路:

快慢指针法

进行一个循环,先让快指针走两步,然后让慢指针走一步,直到快指针指向空或者快指针的next指向空,这时候的慢指针就指向了中间结点,并且也满足第二个结点。

代码:

struct ListNode* middleNode(struct ListNode* head)
{
    //快慢指针,快指针走两步,慢指针走一步
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

三、链表中倒数第k个结点

牛客网链接

题目描述:

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

思路:

也是快慢指针的思想。

先让快指针走k步,然后再让快指针和慢指针一起走,直到快指针为空

这题有一些注意细节的点,比如k大于链表结点的个数,k==0,但这些都是小细节,主要思想还是快慢指针~

 代码:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    if(pListHead==NULL||k==0)//k=0和链表为空的情况
    {
        return NULL;
    }
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    while(k--)//先让快指针走k步
    {
        fast=fast->next;
        if(fast==NULL)
        {
            break;
        }
    }
    if(k>0)//k大于链表结点的个数的情况
    {
        return NULL;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

四、反转链表

leetcode链接

题目描述:

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

思路:

顺序遍历链表,从第一个结点开始进行尾插,注意这里的尾插不是手撕单链表里面的pushback函数,而是应该将结点一个一个取下来。

相当于我们又学习了另外一种尾插的方式,不是直接改变头节点的值,而是将原有的头节点指向新的头节点。

代码:

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead=NULL;
    struct ListNode* next=NULL;
    //头插
    while(head)
    {
        next=head->next;
        head->next=newhead;
        newhead=head;
        head=next;
    }
    return newhead;
}

 五、合并两个有序链表

leetcode链接

题目描述:

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

思路:

两个链表的第一个结点顺序比较,取小的尾插到一个新的头结点上,若一个提前结束,则将另一个直接尾插到新链表上

代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    //取小的尾插
    //为何这题可以直接定义一个尾结点?
    struct ListNode* newhead=NULL;
    struct ListNode* tail=NULL;
    while(list1 && list2)
    {
        if(list1->val <= list2->val)
        {
            if(newhead==NULL)
            {
                newhead=tail=list1;
                //tail=newhead->next;
            }
            else
            {
                tail->next=list1;
                //tail=list1->next;
                tail=tail->next;
            }
            list1=list1->next;
        }
        else
        {
            if(newhead==NULL)
            {
                tail=newhead=list2;
                //tail=newhead->next;
            }
            else
            {
                tail->next=list2;
                tail=tail->next;
            }
            list2=list2->next;
        }
    } 
    if(list1)//剩余直接尾插
    {
        //tail=list1;
        tail->next=list1;
    }  
    if(list2)
    {
        //tail=list2;
        tail->next=list2;
    }
    return newhead;
}    

小心得:

在数据结构的新篇章里,注意的小细节更多,最好将能考虑的情况都要考虑到,不然调试起来比较麻烦。一般只有将头结点为空的情况下,直接赋值等于,其余一般都需要进行next链接。