【Leetcode-链表强训】

每天都要进步呀

发布于 2023-03-28 11:37:29

1810

发布于 2023-03-28 11:37:29

文章被收录于专栏：C++/Linux

链表强训

1.前言

Hello小伙伴们，最新的刷题章节更新了，本篇文章是对链表的训练，为大家准备了三道题，这三道题在我们之前训练的基础上实现起来不是很困难，当然，如果之前没有训练过的小伙伴们，可以先看这个章节呀：链表总结
那么，在大家已有的基础之上，我们开始对下面的三道oj进行逐一的讲解：

LeetCode.92.反转链表（2）

1. 题目

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

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

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

2.思路推导

在这道题开始之前我们知道反转链表有两种方式，分别是迭代和头插，对于此题，本质上仍然是变式之前的反转链表，只不过有了范围，那我们就将这个范围的链表单拿出来，这里指的单拿出来是将其两端区间断开，并记录新的头，也就是左区间的第一个节点，断开的目的是让在这个区间的链表单独反转，如果不断开或者只断开左面的节点，将会导致区间外的链表节点跟着反转。

第一步：将需要反转的链表断开，并记录连接的位置

第二步：将断开的链表进行反转（两种方法，此例用的迭代）

第三步：连接链表

那么有了大致过程，就可以上代码了：

3. 代码实现

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

// 思路： 将区间两侧的节点记录好，然后将这个区间两侧断开单拿出来反转，反转之后再将其两侧进行连接

struct ListNode* reverse(struct ListNode* head)//反转链表
{
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* next = head->next;

    while(cur)
    {
        cur->next = prev;

        prev = cur;
        cur = next;
        if(next)
            next = next->next;
    }
    return prev;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
     if(head == NULL || head->next == NULL||left == right)
     {
         return head;
     }
     struct ListNode* cur = head;
     struct ListNode* lprev = NULL;
     struct ListNode* rafter = NULL;

     //找左端点
     while(--left)
     {
         lprev = cur;
         cur = cur->next;
     }

     //找右端点
     cur = head;
     while(--right)
     {
         cur = cur->next;
     }
     //看左端点是否为空，为空代表从第一个节点开始反转
     if(lprev)
     {
         struct ListNode* reverhead = lprev->next;
         lprev->next = NULL;
         struct ListNode* afterhead = cur->next;//afterhead代表rafter
         cur->next = NULL;
         struct ListNode* rev = reverse(reverhead);
         lprev->next = rev;
         while(rev->next)
         {
             rev = rev->next;
         }
         rev->next = afterhead;
         return head;
     }
     else
     {
         struct ListNode* afterhead = cur->next;
         cur->next = NULL;
         struct ListNode* rev = reverse(head);
         struct ListNode* now = rev;
         while(now->next)
         {
             now = now->next;
         }
         now->next = afterhead;
         return rev;
     }
}

LeetCode.445.两数相加（2）

1. 题目

445. 两数相加 II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

**进阶：**如果输入链表不能翻转该如何解决？

2. 思路推导

将两个链表分别反转之后，就可以遍历两个链表然后相加，不过，我们应该选择一个长的链表为基础，让此节点的 val1 = val1+val2 ,并且应该将这个基础链表再尾插一个新的节点，让这个节点的val=0，目的是为了进位用，然后再将这个长链表反转，如果头（此时的头为新尾插的节点）的val = 0，则free掉这个头，让head指向下一个节点。

第一步：反转两个链表

第二步：为长的链表增加一个节点，相加

第三步：反转回来，并去0

3. 代码实现

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

struct ListNode* reverse_list(struct ListNode* head)
{
    if(head == NULL||head->next==NULL)
        return head;
    struct ListNode* newHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;

}
int lenth_list(struct ListNode* head)
{
    struct ListNode* cur = head;
    int len = 0;
    while(cur)
    {
        cur = cur->next;
        len++;
    }
    return len;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* rev1 = reverse_list(l1);
    struct ListNode* rev2 = reverse_list(l2);
    int large = lenth_list(rev1);
    int small = lenth_list(rev2);
    struct ListNode* longth = rev1;
    struct ListNode* shorth = rev2;
    if(large<small)
    {
         longth = rev2;
         shorth = rev1;
    }
    struct ListNode* cur = longth;//长的
    struct ListNode* curs = shorth;
    while(cur->next)
    {
        cur = cur->next;
    }
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->val = 0;
    newnode->next = NULL;
    cur->next = newnode;
    
    cur = longth;
    int carry = 0;
    while(cur && curs)
    {
        cur->val +=curs->val+carry;
        if(cur->val>9)
        {
            carry = cur->val/10;
            cur->val %=10;
        }
        else
        {
            carry = 0;
        }
        cur = cur->next;
        curs = curs->next;
    }
    while(cur)
    {
        cur->val = cur->val+carry;
        
        if(cur->val>9)
        {
            carry = cur->val/10;
            cur->val %=10;
        }
        else
        {
            carry = 0;
        }
        cur = cur->next;
    }
    struct ListNode* phead = reverse_list(longth);
    if(phead->val == 0)
    {
        struct ListNode* del = phead;
        phead = phead->next;
        free(del);
    }
    return phead;
}

LeetCode.1019. 链表中的下一个更大节点

1. 题目

1019. 链表中的下一个更大节点

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

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

示例 2：

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

提示：

链表中节点数为 n
1 <= n <= 104
1 <= Node.val <= 109

2. 思路推导

对于这道题，服从题干的思路即可，即暴力解决，需要注意的是记得将*returnSize 赋值， *returnSize代表返回元素的个数。

3. 代码实现

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


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//暴力解决：按着题目要求来即可
int list_size(struct ListNode* head)
{
    if(head == NULL)
        return 0;
    struct ListNode* cur = head;
    int count = 0;
    while(cur)
    {
        cur = cur->next;
        count++;
    }
    return count;
}
int* nextLargerNodes(struct ListNode* head, int* returnSize){
    int len = list_size(head);
    *returnSize = len;
   int* arr = (int*)calloc(len,sizeof(int));
   int i = 0;
   struct ListNode* cur = head;
   while(cur)
   {   struct ListNode* cnext = cur->next;
       struct ListNode* next = cur->next;
       if(next!=NULL)
       {
           while(next)
           {
               if(cur->val<next->val)
               {
                   arr[i++] = next->val;
                   break;
               }
               next = next->next;
           }
           if(next == NULL)
           {
               arr[i++] = 0;
           }
       }
       else
       {
           arr[i++] = 0;
       }
       cur = cnext;
   }
   return arr;

}