刷爆leetcode第三期 0007~0010-EW帮帮网

刷爆leetcode第三期 0007~0010

题目一反转链表

解法一

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/UHnkqh

还是一样我们画图来分析下

在这里插入图片描述

代码表示如下

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return head;
    }
    struct ListNode* prev =NULL;
    struct ListNode* pos = head;
    struct ListNode* next = head;
    prev = pos;
    pos = pos->next;
    prev->next = NULL;
    while(pos)
    {
        next = pos;
        pos = pos->next;
        next->next =prev;
        prev = next;
    }

    return next;

}

这就是解法一思路很简单也可以很顺畅的运行

解法二

还是先画图给大家看看

在这里插入图片描述

在这里插入图片描述
代码表示如下

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* next =NULL;
    struct ListNode* pos =NULL;

    pos = head;
    next = head;

    while(next)
    {
        next = next->next;
        pos->next = newhead;
        newhead = pos;
        pos = next;

    }

    return newhead;

}

题目二链表的中间节点

在这里插入图片描述
这道题目就是一个经典的快慢指针问题

我们可以设置两个指针

慢指针先走每次走一格

快指针再走每次走两格

当快指针指向最后一个节点或者是空指针的时候直接return slow就可以

代码表示如下

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

    while ((fast!=NULL)&&(fast->next!=NULL))
    {
        slow=slow->next;
        fast=fast->next->next;
    }

    return slow;

}

很简单大家领悟一下思路就可以

题目三链表的倒数第K个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

还是跟上面的题思路一样

还是一个快慢指针的问题

在这里插入图片描述
这里要求倒数k个位置

只需要让fast先走k步就可以

放fast走到NULL的时候return solw的值

当然这里要注意如果说fast走到了NULL k还没有归零

那么这个时候就要返回空指针了

代码表示如下

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    struct ListNode* slow =head;
    struct ListNode* fast = head;

    while(fast && k--)
    {
        fast =fast->next;
    }
    if((fast==NULL) && (k>0))
    {
        return fast;
    }

    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }


    return slow;


}

题目四合并两个有序链表

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

在这里插入图片描述
画图这样子就很好理解

当然这里要考虑两个特殊情况

在这里插入图片描述

如果说像这样子 l2数组为空那么只需要将head = l1

返回head就可以

反之亦然

代码表示如下

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    if(list1==NULL)
    {
        head = list2;
        return head;
    }
    if(list2==NULL)
    {
        head =list1;
        return head;
    }

    while(list1 && list2)
    {
        if((list1->val)<(list2->val))
        {
            if(head == NULL)
            {
                head = tail =list1; 
            }
            else
            {
                tail ->next = list1;
                tail=tail->next;
            }

            list1=list1->next;
            
        }
        else
        {
            if(head == NULL)
            {
                head = tail =list2; 
            }
            else
            {
                tail ->next = list2;
                tail=tail->next;
            }

            list2=list2->next;
        }
    }

    if(list1)
    {
        tail->next=list1;
    }
    else
    {
        tail->next=list2;
    }
    return head;
}

刷爆leetcode第三期 0007~0010