力扣刷题第一天:剑指 Offer 18. 删除链表的节点、LC206.反转链表

简介: 力扣刷题第一天:剑指 Offer 18. 删除链表的节点、LC206.反转链表

零、前言


这篇文章主要讲解两道链表相关的题目,分别是剑指 Offer 18和LC206。链表作为数据结构中重要的一环,相信在面试和日常编程中都有很大的用处。因此,掌握链表的基本操作以及部分高级应用,对于程序员来说尤为重要。


在本文中,我们将从题目描述、解题思路以及完整代码三个方面出发,深入浅出地为大家讲解如何解决这两道链表问题,并希望能够对大家在学习链表时有所帮助。


剑指 Offer 18. 删除链表的节点


c4da1cc072b746b48b15807561ee3cab.png


一、题目描述


给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:


输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.


示例 2:


输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.


二、解题思路:


这道题的基本思路就是遍历整个链表,找到待删除节点的前一个节点,然后将其指针指向待删除节点的下一个节点即可。但需要注意的是,如果待删除节点是头节点,那么需要特殊处理。具体来说,可以添加一个哨兵节点,使得头节点不会成为特殊情况。


二、解题思路

题目已经给出了它的单链表结构:

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


这道题的思路很简单,遍历整个链表,找到待删除节点的前一个节点,然后将其指针指向待删除节点的下一个节点即可。只不过需要注意的地方是,如果要删除的是头结点,那我们该如何去处理?


三、完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode* cur = head;
struct ListNode* prev = NULL;
    while(cur&&cur->val!=val)
    {
        if(cur->val==val)
        break;
        prev = cur; //后继结点保存当前前驱结点的作用
        cur = cur->next; //前驱结点指向下一个结点
    }
    if(cur==NULL) //如果后继结点为空,那就说明没有找到
    {
         return head; //返回头结点
    }
    if(prev==NULL) //找到了该结点
    {
        head = cur->next; // 将需要删除的结点指向后继节点的前驱结点
    }
    else{
        prev->next = cur->next;  // 将prev的下一个结点指向cur的下一个结点
    }
    free(cur);
    return head;
}

cc4e29dd095f4a46993388e9729240d7.png


LC206.反转链表


69bf7aac4aa14e5bae0803746904a827.png


一、题目描述


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

示例 1:

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

示例 2:

输入:head = [1,2] 输出:[2,1]

示例 3:

输入:head = [] 输出:[]


二、解题思路


这道题可以用迭代或递归两种方法来解决。

首先介绍迭代方法,具体实现如下:


创建三个指针 prev、curr 和 next,分别表示前一个节点、当前节点和下一个节点。并令 curr = head,prev 和 next 初始化为 NULL。

循环遍历链表,直到 curr 为空。在每一次循环中: a. 记录当前节点的下一个节点,即 next = curr->next; b. 将当前节点的指针指向前一个节点,即 curr->next = prev; c. 将前一个节点 p 和当前节点 q 同时后移一位,即 prev = curr; curr = next;

最终返回 prev 即可。


三、完整代码


struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL) //如果链表为空,直接返回head
    return head;
    struct ListNode* cur = head,*prev = NULL,*next = NULL; //创建三个指针
    while(cur)
    {
        next = cur->next; // next保存cur的下一个结点
        cur->next=  prev; //cur的下一个结点指向prev
        prev = cur; //prev保存cur的地址
        cur = next; //cur再重新指向next
    }
    return prev; //返回新的头结点
}


欢迎访问我的gitee仓库 : My Gitte repository 代码+图解: Night Cruising (gitee.com)

里面有基础数据结构的实现(还不完整)和OJ题解(还在补充)在内,欢迎各位大佬指(多)点(多)一(包)番(涵)!!

相关文章
|
4月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
49 1
|
4月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
63 0
Leetcode第21题(合并两个有序链表)
|
4月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
42 0
LeetCode第二十四题(两两交换链表中的节点)
|
4月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
53 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
4月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
64 0
|
4月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
34 0
|
4月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
119 0
|
5月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
73 6
|
6月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
145 2