数据结构-单链表-力扣题

2023-11-10 19:52
文章标签 数据结构 单链 力扣题

本文主要是介绍数据结构-单链表-力扣题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

移除链表元素

反转链表

链表的中间节点

返回倒数第k个节点 

合并两个有序列表 

分割链表

链表的回文结构

 相交链表：找两个链表的公共节点

环形链表：判断链表中是否有环

 环形链表 II：要求返回入环的第一个节点

移除链表元素

题目链接：力扣（LeetCode）

思路：和前面学的单链表的中间删除数据一样，使要被删除节点的前一个节点指向下要被删除节点的下一个节点，然后把要被删除的节点free掉。

 具体实现过程：先定义prev和cur，让cur指向头节点，遍历链表，如果cur->val!=val，让prev指向cur，cur指向cur的下一个节点，（prev始终在cur前面一个节点），当cur->val=val时停下，让prev的下一个节点指向cur的下一个节点，删除它们中间的cur节点，然后让cur重新指向prve->next，这就实现了节点的删除。但是还有一种情况如下图：

头节点的数据等于val，这时就需要判断了，如果头节点数据等于val，就要删除头节点，然后把head重新指向原来的头结点的下一个节点，cur重新指向head：

代码如下：

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode*prev=NULL;struct ListNode*cur=head;while(cur!=NULL){if(cur->val==val){if(prev){prev->next=cur->next;free(cur);cur=prev->next;}else{head=cur->next;free(cur);cur=head;}}else{prev=cur;cur=cur->next;}}return head;
}

这道题还有一道解法，就是重新开辟一个节点，找到不相等的节点，尾插到该节点的后面

直接上代码：

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead=NULL;struct ListNode* cur=head;struct ListNode* tail=NULL;while(cur!=NULL){if(cur->val!=val){if(newhead == NULL){tail=newhead=cur;}else{tail->next = cur;tail = cur;}cur=cur->next;tail->next=NULL;}else{struct ListNode* next = cur->next;free(cur);cur = next;}}return newhead;
}

反转链表

题目链接：力扣（LeetCode） 

思路：逆转链表中所有的箭头指向，如下图所示：

 首先，定义n1为null，定义n2为原链表的头节点，只要使n2下一个指向的是n1，然后把n2给你，n3给n2，这样进行迭代，直到链表的所有箭头全部反转，就实现了反转链表，注意：在每次循环开始的时候都要用n3保存n2的下一个节点位置，否则，n2改变指向后就找不到后面的节点了。

代码如下：（代码中用rhead替代n1，用cur替代n2，用next替代n3）

struct ListNode* reverseList(struct ListNode* head) {struct ListNode*cur=head;struct ListNode*rhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=rhead;rhead=cur;cur=next;}return rhead;
}

链表的中间节点

题目链接：力扣（LeetCode）

思路：定义快慢指针fast和slow，fast每次走两步，slow每次走一步，如果有奇数个节点，当fast走到最后一个节点时，slow就走到中间节点了，如果有偶数个节点，当fast走到空，slow就走到中间节点了。

 因此我们在循环时要判断，当fast和fast->next为空时就不能再继续了。

代码如下：

struct ListNode* middleNode(struct ListNode* head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

返回倒数第k个节点 

 题目链接：力扣（LeetCode）

思路一： 上文我们讲了如何反转链表，这道题可以复用反转链表，先把链表整体反转，然后从前往后找第k个节点。

代码如下：

int kthToLast(struct ListNode* head, int k){struct ListNode*cur=head;struct ListNode*rhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=rhead;rhead=cur;cur=next;}while(--k){rhead=rhead->next;}return rhead->val;
}

思路二： 定义快慢指针fast和slow，先让fast走k步（或者k-1步），然后slow和fast一起走，直到fast为空就停止（如果先让fast走k-1步，则当fast->next为空时停止），这时slow节点就是要找的倒数第k个节点。 

fast先走k步： 

int kthToLast(struct ListNode* head, int k){struct ListNode*fast=head;struct ListNode*slow=head;while(k--){fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow->val;
}

fast先走k-1步： 

int kthToLast(struct ListNode* head, int k){struct ListNode*fast=head;struct ListNode*slow=head;int n=k-1;while(n--){fast=fast->next;}while(fast->next){slow=slow->next;fast=fast->next;}return slow->val;
}

合并两个有序列表 

题目链接：力扣（LeetCode） 

思路： 创建一个新链表，比较链表list1和list2中的值，每次把较小的尾插在新节点的后面（如果相等，随便取其中一个尾插），直到链表list1和list2中有一个被遍历完，就停止循环。此时，如果list1先结束，list2中有剩余的节点，直接把剩下的节点尾插到新链表后面；同理，如果list2先结束，list1中有剩余，就把list1中剩余的节点位插到新链表后面。注意：如果list1开始就为空，直接返回list2；如果list2开始就为空，直接返回list1。

代码如下： 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode*newhead=NULL;struct ListNode*tail=newhead;if(list1==NULL)return list2;if(list2==NULL)return list1;while(list1&&list2){if((list1->val)<=(list2->val)){if(tail==NULL){tail=newhead=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(tail==NULL){tail=newhead=list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1)tail->next=list1;if(list2)tail->next=list2;return newhead;
}

上述代码看起来很复杂，因为在刚开始的时候，不管是list1大，还是list2大，我们都要判断新链表的头结点是不是为NULL，那如何能简化这个问题呢？

这里我们来介绍一下哨兵位的头结点，哨兵位的头结点不存储有效数据，哨兵位的头结点相当于我们新开辟的一个节点，可以直接在其后面尾插而不用担心它是不是NULL，下图就是头结点和带哨兵位的头结点之间的区别：

下面我们用哨兵位来实现一下上题：

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

这就是哨兵位的优势了，当我们用malloc开辟一个新节点newhead，就可以直接在它后面尾插，最后把newhead指向它的下一个节点，然后释放newhead就行。哨兵位的使用让我们省略了很多判断过程。 

分割链表

题目链接：力扣（LeetCode）

思路：我们可以使用哨兵位的头节点，分别开辟一个“大链表”和“小链表”的头结点，把原链表中的比x小的尾插到小链表的头结点之后，把比x大的尾插到大链表的头结点之后，遍历完原链表，把大链表整体尾插到小链表后面，具体如下图：

 注意：最后要将哨兵位头结点释放掉。

这道题比较复杂，分很多种情况：

1.链表为空   

2.链表元素全大于x   

3.链表元素全小于x   

4.有大有小

代码如下：

struct ListNode* partition(struct ListNode* head, int x){//链表为空if(head==NULL) return NULL;//链表全小于xint l = 0;struct ListNode* tmp = head;while(tmp){if(tmp->val>=x){l = 1;}tmp = tmp->next;}if(l == 0){return head;}tmp = head;//链表全大于xint g = 0;while(tmp){if(tmp->val<=x){g = 1;}tmp = tmp->next;}if(g == 0){return head;}struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=head;while(cur){if(cur->val<x){lesstail->next=cur;lesstail=lesstail->next;}else{greatertail->next=cur;greatertail=greatertail->next;}cur=cur->next;}lesstail->next=greaterhead->next;greatertail->next=NULL;head=lesshead->next;free(lesshead);free(greaterhead);return head;
}

链表的回文结构

题目链接：链表的回文结构_牛客题霸_牛客网

 思路：这道题可以根据上面的题目代码来实现，先找到中间节点，然后把中间节点往后的链表反转，使用双指针，指针1从头节点开始，指针2从中间节点开始，比较它们的值，如果相等，分别往后移一位，直到指针2指向空，说明就是回文结构；如果不相等，说明不是回文结构。

代码如下：

class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}struct ListNode* reverseList(struct ListNode* head) {struct ListNode*cur=head;struct ListNode*rhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=rhead;rhead=cur;cur=next;}return rhead;
}bool chkPalindrome(ListNode* phead) {struct ListNode*mid=middleNode(phead);struct ListNode*rmid=reverseList(mid);while(rmid){if(phead->val==rmid->val){phead=phead->next;rmid=rmid->next;}else{return false;}}return true;}
};

 相交链表：找两个链表的公共节点

题目链接：力扣（LeetCode）

思路： 首先先判断它们是不是相交链表，只要判断它们的尾节点是不是相同的就行，只要尾节点相同就必定相交，因为相交链表只能是"Y"型的，不可能是"X"型的，下面就要返回相交链表的公共节点了，可以计算一下两个链表的长度，让长链表先走长度差步，然后两个链表一起走，如果有相同节点，该节点就是公共节点，如果没有，说明两个链表没有公共节点。

代码如下：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*tailA=headA;struct ListNode*tailB=headB;int lenA=0;int lenB=0;while(tailA->next){tailA=tailA->next;lenA++;}while(tailB->next){tailB=tailB->next;lenB++;}if(tailA!=tailB){return NULL;}int gap=abs(lenA-lenB);struct ListNode*longlist=headA;struct ListNode*shortlist=headB;if(lenA<lenB){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

环形链表：判断链表中是否有环

题目链接：力扣（LeetCode)

思路：使用快慢指针，快指针一次走两步，慢指针一次走一步，如果有环，快指针先进环，慢指针后进环，快指针一定会某一时刻追上慢指针，此时它们相等。如果没环，快指针一定会最终指向空。

代码如下：

bool hasCycle(struct ListNode *head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow)return true;}return false;
}

 环形链表 II：要求返回入环的第一个节点

题目链接：力扣（LeetCode） 

思路：双指针法，一个指针从头节点处开始走，一个指针从相遇处的节点开始走，当它们相等时就是入环节点。

推导过程：

代码如下：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){struct ListNode*meet=fast;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL;
}

这篇关于数据结构-单链表-力扣题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/384906。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
Go语言构建单链表

Go语言构建单链表

package mainimport "fmt"type ListNode struct {Val intNext *ListNode}func main() {list := []int{2,4,3}head := &ListNode{Val:list[0]}tail := head //需要头尾两个指针for i:=1;i<len(list);i++ {//方法一 数组直接构建链表tai
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2