链表相关部分OJ题

简介: 链表相关部分OJ题

❣️1.206.反转链表


💘1.题目

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


示例 1:

image.png


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

输出:[5,4,3,2,1]

示例 2:

image.png


输入:head = [1,2]

输出:[2,1]

示例 3:


输入:head = []

输出:[]


提示:


链表中节点的数目范围是 [0, 5000]

-5000 <= Node.val <= 5000



💘2.解答:

💓1.遍历法

image.png


创建3个指针n1、n2、n3,分别指向反转后的头节点、当前节点(初始化为head)、当前节点的后一个节点。初始化n1为NULL。

进入循环,循环条件为n2非NULL。在循环中,首先将n2指向n1,实现当前节点的反转。

然后让n1指向n2,将n1更新为反转后的头节点。

再让n2指向n3,将当前节点指向下一个节点。

如果n3非NULL,则让n3指向其下一个节点。

循环结束后,返回n1,即为反转后的头节点。

这里值得注意的是,需要先判断head是否为NULL,如果是,则直接返回NULL,否则会出现空指针异常。


struct ListNode* reverseList(struct ListNode* head)
{
if(head == NULL)
return NULL;
struct ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
return n1;
}


💓2.头插法

从头节点 head 开始遍历链表,每次将当前节点 cur 的 next 指针指向新链表的头节点 newhead,然后将 newhead 更新为 cur,最后将 cur 移向下一个节点。这相当于不断将原链表的节点从头部插入到新链表中,从而实现了链表的反转。

最终返回新链表的头节点 newhead,即为原链表反转后的链表头。


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

❣️2.   牛客.链表中倒数第k个结点  


💘1.题目

描述

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

示例1

输入:

1,{1,2,3,4,5}

返回值:

{5}

💘2.解答    

 

定义两个指针slow和fast,初始都指向链表头节点pListHead。

让fast先走k步,如果fast为空,则返回NULL,因为链表长度小于k,找不到倒数第k个节点。

然后slow和fast同时走,直到fast到达链表末尾。

最后返回slow所指向的节点即可。


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
 {
    struct ListNode* slow = pListHead,*fast = pListHead;// write code here
// fast先走k步
while(k--)
{
if(fast == NULL)
return NULL;
fast = fast->next;
}
// 同时走
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
 }

❣️ 3.160.相交链表  


💘1.题目

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。


图示两个链表在节点 c1 开始相交:


题目数据 保证 整个链式结构中不存在环。


注意,函数返回结果后,链表必须 保持其原始结构 。


自定义评测:


评测系统 的输入如下(你设计的程序 不适用 此输入):


intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数

skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。



示例 1:

image.png

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出:Intersected at '8'

解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。

在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。


示例 2:

image.png

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出:Intersected at '2'

解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。

在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。


示例 3:

image.png



输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出:null

解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。

由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

这两个链表不相交,因此返回 null 。


提示:


listA 中节点数目为 m

listB 中节点数目为 n

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点,intersectVal 为 0

如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]


💘2.解答

函数首先遍历链表A和链表B,找到它们的尾结点并计算它们的长度。如果两个链表的尾结点不同,则它们不可能相交,直接返回NULL指针。

如果两个链表相交,则它们必须有共同的尾部。接下来,找到两个链表的差距,记为n。如果链表B的长度大于链表A,则将longList指向链表B,shortList指向链表A,否则将longList指向链表A,shortList指向链表B。然后让longList先走n步,然后longList和shortList一起走,直到它们相遇,即为它们的交点。

最后返回交点的地址。


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
 {
struct ListNode* curA = headA,*curB = headB;
int lenA = 1,lenB = 1;
// 找尾结点,顺便算一下长度
while(curA->next)
{
lenA++;
curA = curA->next;
}
while(curB->next)
{
lenB++;
curB = curB->next;
}
//判断相交
if(curA != curB)
{
return NULL;
}
int n = abs(lenA-lenB);
struct ListNode* longList = headA,*shortList = headB;
if(lenB > lenA)
{
longList = headB;
shortList = headA;
}
// 长的先走差距步
while(n--)
{
longList = longList->next;
}
// 同时走
while(longList != shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
   
}


❣️4.141.环形链表  


💘1.题目

给你一个链表的头节点 head ,判断链表中是否有环。


如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。


如果链表中存在环 ,则返回 true 。 否则,返回 false 。


示例 1:

image.png

输入:head = [3,2,0,-4], pos = 1

输出:true

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

image.png

输入:head = [1,2], pos = 0

输出:true

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

image.png

输入:head = [1], pos = -1

输出:false

解释:链表中没有环。


提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos-1 或者链表中的一个 有效索引

💘2.解答

定义两个指针slow和fast,初始值均指向head节点。

在循环中,slow每次移动一步,fast每次移动两步,如果存在环,那么fast最终一定会追上slow。

在每次移动后,判断slow和fast是否指向同一个节点,如果是,则存在环,返回true。

如果循环结束后仍然没有找到环,则不存在环,返回false。

因为快指针每次移动两步,慢指针每次移动一步,所以如果存在环,快指针一定可以追上慢指针。而如果不存在环,快指针最终会到达链表尾部,循环结束。


bool hasCycle(struct ListNode *head){
struct ListNode*slow =head,*fast =head;
while(fast &&fast->next)
{
slow =slow->next;
fast =fast->next->next;
if(slow ==fast)
return true;
}
return false;
}
相关文章
|
1月前
数据结构——链表OJ题
数据结构——链表OJ题
|
1月前
|
存储
2023 8 -14链表OJ(上)
2023 8 -14链表OJ
38 0
|
1月前
链表OJ详解
链表OJ详解
30 0
|
26天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
24 0
|
26天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
25 0
|
26天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
16 0
|
26天前
|
算法 测试技术
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(下)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
24 0
|
26天前
|
算法
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(上)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
14 0
|
26天前
11道链表oj题
11道链表oj题
19 0
|
1月前
|
算法
顺序表、链表相关OJ题(2)
顺序表、链表相关OJ题(2)