链表相关部分OJ题

d544c1a6847e450b926aa15e8ee02964.jpeg

❣️1.206.反转链表

💘1.题目

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

示例 1：

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

输入：head = [1,2] 输出：[2,1] 示例 3：

输入：head = [] 输出：[]

提示：

链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000

💘2.解答：

💓1.遍历法

1. 创建3个指针n1、n2、n3，分别指向反转后的头节点、当前节点（初始化为head）、当前节点的后一个节点。初始化n1为NULL。
2. 进入循环，循环条件为n2非NULL。在循环中，首先将n2指向n1，实现当前节点的反转。
3. 然后让n1指向n2，将n1更新为反转后的头节点。
4. 再让n2指向n3，将当前节点指向下一个节点。
5. 如果n3非NULL，则让n3指向其下一个节点。
6. 循环结束后，返回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.解答

1. 定义两个指针slow和fast，初始都指向链表头节点pListHead。
2. 让fast先走k步，如果fast为空，则返回NULL，因为链表长度小于k，找不到倒数第k个节点。
3. 然后slow和fast同时走，直到fast到达链表末尾。
4. 最后返回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：

输入：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：

输入：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：

输入：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：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

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

💘2.解答

1. 定义两个指针slow和fast，初始值均指向head节点。
2. 在循环中，slow每次移动一步，fast每次移动两步，如果存在环，那么fast最终一定会追上slow。
3. 在每次移动后，判断slow和fast是否指向同一个节点，如果是，则存在环，返回true。
4. 如果循环结束后仍然没有找到环，则不存在环，返回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;
}