【初阶数据结构】3.单链表

文章目录

  • 3.单链表
    • 3.1 概念与结构
      • 3.1.1 结点
      • 3.1.2 链表的性质
      • 3.1.3 链表的打印
    • 3.2 实现单链表
    • 3.3 链表的分类
    • 3.4 单链表算法题
      • 3.4.1 移除链表元素
      • 3.4.2 反转链表
      • 3.4.3 链表的中间结点
      • 3.4.4 合并两个有序链表
      • 3.4.5 链表分割
      • 3.4.6 链表的回文结构
      • 3.4.7 相交链表
      • 3.4.8 环形链表I
      • 3.4.9 环形链表II
      • 3.4.10 随机链表的复制

3.单链表

3.1 概念与结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

链表就像车厢一样。

在这里插入图片描述

3.1.1 结点

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

图中指针变量 plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

3.1.2 链表的性质

  1. 链式机构在逻辑上是连续的，在物理结构上不一定连续
  2. 结点一般是从堆上申请的
  3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前面学到的结构体知识，我们可以给出每个结点对应的结构体代码：

struct ListNode
{int data; //结点数据struct ListNode* next; //指针变量用保存下一个结点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址为空）。

当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。

3.1.3 链表的打印

给定的链表结构中，如何实现结点从头到尾的打印？

!在这里插入图片描述

3.2 实现单链表

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>//定义链表（结点）的结构typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//链表的头
void SLTPrint(SLTNode* phead);//增加数据
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphaed, SLTDataType x);//删除
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include"SList.h"
#include <assert.h>//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur) {printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//申请新节点
SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL) {perror("malloc fail !");exit(1);}node->data = x;node->next = NULL;return node;
}//增加数据
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//申请新节点SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL) {*pphead = newnode;}else {//尾结点和新结点连接//找尾结点SLTNode* pcur = *pphead;while (pcur->next) {pcur = pcur->next;}//pcur和newnode连接pcur->next = newnode;}	
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//删除
//尾删
void SLTPopBack(SLTNode** pphead) {//链表为空，不能删除assert(pphead && *pphead);//处理只有一个节点的情况：要删除的就是头节点if ((*pphead)->next == NULL) {//->的优先级比*高，所以要加个（）free(*pphead);*pphead = NULL;}else {//找尾结点 prev（尾结点的前一个结点） ptail（尾结点）SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next) {prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//用一个指针存放第二个节点free(*pphead);*pphead = next;//头指向存放的地方
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* pcur = phead;while (pcur) {if (pcur->data == x) {//当前这个结点存的是不是xreturn pcur;}pcur = pcur->next;}//没有找到return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);if (pos == *pphead) {SLTPushFront(pphead, x);//调用头插}else {SLTNode* newnode = SLTBuyNode(x);//找prev：pos的前一个节点SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead && *pphead);assert(pos);if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos) {assert(pos && pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SListDestroy(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur) {SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include"SList.h"//创建一个链表，并打印链表void createSList() {//链表是由一个一个的结点组成的SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//把第一个结点的地址作为参数传递过去SLTNode* plist = node1;SLTPrint(node1);}void SListTest01() {SLTNode* plist = NULL;/*SLTPushBack(plist, 1);SLTPrint(plist);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPrint(plist);*/SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist);//4->3->2->1->NULL//SLTPopBack(&plist);//SLTPrint(plist);//4->3->2->NULL//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist); //3->2->1->NULL//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);SLTNode* find = SLTFind(plist, 2);/*if (find == NULL) {printf("未找到！\n");}else {printf("找到了！\n");}*///SLTInsert(&plist, find, 11);//11->4->3->2->1->NULL//SLTInsertAfter(find, 11);//4->3->2->1->11->NULL//SLTErase(&plist, find);//SLTEraseAfter(find);SListDestroy(&plist);//销毁SLTPrint(plist);
}int main() {//createSList();SListTest01();return 0;
}

3.3 链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

在这里插入图片描述

链表说明：

在这里插入图片描述

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表
  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.4 单链表算法题

3.4.1 移除链表元素

点击链接做题

在这里插入图片描述

思路1：遍历链表，在原链表执行删除指定节点的操作。

思路2：创建新链表，将原链表中值不为val的结点尾插到新链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建新链表ListNode* newHead,*newTail;newHead = newTail = NULL;//遍历原链表ListNode* pcur = head;while(pcur){//找值不为val的结点，往新链表中进行尾插if(pcur->val != val){//尾插//链表为空if(newHead == NULL){newHead = newTail = pcur;}//链表不为空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if(newTail){newTail->next = NULL;}return newHead;}

3.4.2 反转链表

点击链接做题

在这里插入图片描述

思路1：把第一个链表头插到一个新链表

思路2：创建3个指针，n1,n2,n3，在原链表上就可以修改指针的指向（不需要创建新的链表）

思路2代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {//处理空链表if(head == NULL){return head;}//创建3个指针ListNode* n1, *n2, *n3;n1 = NULL;n2 = head;n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}//此时的n1就是链表反转后新的头节点return n1;
}

3.4.3 链表的中间结点

点击链接做题

在这里插入图片描述

思路1：

  1. 第一次循环：求链表总长度，计算中间结点的位置
  2. 第二次循环：根据中间节点的位置走到中间节点

思路2：快慢指针

先定义快慢指针fast,slow，都位于头节点

慢指针每次往后走1步，快指针每次往后走2步。

奇数个结点时：当fast->next == NULL就没有必要往后走了，此时slow也刚好指向中间节点

偶数个结点时：当fast走到NULL的时候，此时slow也刚好指向中间节点

为什么快慢指针可以找到中间节点?

慢指针每次走一步，快指针每次走两步，当快指针走到链表的尾结点时，假设链表的长度为n

快指针走的路程是慢指针的两倍，即2*慢=快

此时慢指针走的路程就是n/2

思路代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head, *fast = head;//慢指针每次走1步，快指针每次走2步while(fast && fast->next){//不能写while(fast->next && fast)slow = slow->next;fast = fast->next->next;}//此时slow指向的结点刚好就是中间结点return slow;
}

3.4.4 合并两个有序链表

点击链接做题

在这里插入图片描述

思路：创建新链表，遍历原链表，比较大小，谁小就尾插到新链表

思路代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理链表为空的情况if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//创建新的链表ListNode* newHead = NULL,*newTail = NULL;//创建两个指针分别指向两个链表的头节点ListNode* l1 = list1;ListNode* l2 = list2;while(l1 && l2){if(l1->val < l2->val){//l1尾插到新链表中if(newHead == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{//l2尾插到新链表中if(newHead == NULL){newHead = newTail = l2;}else{newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//跳出循环只有两种情况：要么l1为空，要么l2为空if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}return newHead;
}

因为链表分为空和非空两种情况导致代码有点冗余，我们可以通过封装函数或者直接创建一个空链表来解决。

采用后者优化后：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理链表为空的情况if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//创建新的链表ListNode* newHead,*newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));//创建两个指针分别指向两个链表的头节点ListNode* l1 = list1;ListNode* l2 = list2;while(l1 && l2){if(l1->val < l2->val){//l1尾插到新链表中newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{//l2尾插到新链表中newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}//跳出循环只有两种情况：要么l1为空，要么l2为空if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}ListNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}

3.4.5 链表分割

点击链接做题

在这里插入图片描述

例如：

排序前：1->6->2->3->5

X：X = 3

排序后：1->2->6->3->5

思路：

排序前：1->6->2->3->5

小链表：malloc->1->2

大链表：malloc->6->3->5

最后：1->2->6->3->5(把2的next指向6)

思路代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//创建两个非空链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历链表，找小于x的和其他节点尾插到大小链表中ListNode* pcur = pHead;while(pcur){//等价于pcur!=NULLif(pcur->val < x){//尾插到小链表lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//大小链表首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;}
};

上面这个代码提示内存超限，因为有个问题：

例如：

排序前：5->1->3->6->2

小链表：malloc->1->2

大链表：malloc->5->3->6

结果：1->2->5->3->6->2->5->3->6

（因为这里是把2的next指向5，来让两个链表连起来。但是6的next我们没有改，在排序前6的next是2，所以这里会死循环）

我们只要将大链表的尾结点的next指针置为null就可以了

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//创建两个非空链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历链表，找小于x的和其他节点尾插到大小链表中ListNode* pcur = pHead;while(pcur){//等价于pcur!=NULLif(pcur->val < x){//尾插到小链表lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//将大链表的尾结点的next指针置为nullgreaterTail->next = NULL;//大小链表首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;}
};

3.4.6 链表的回文结构

点击链接做题

在这里插入图片描述

思路1：创建新的数组，遍历原链表，遍历原链表，将链表节点中的值放入数组中，在数组中判断是否为回文结构。

例如：

排序前：1->2->2->1

设置数组来存储链表，设置数组头指针left和数组尾指针right

判断left和right指向的数是否相等，相等就left++;right--;，直到left > right

思路代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint arr[900] = {0};int i = 0;ListNode* pcur = A;//遍历链表，将链表中每个节点中的数值储存在数组中while(pcur){arr[i++] = pcur->val;pcur = pcur->next;}//i即结点的个数//找中间节点，判断是否为回文数字int left = 0;//数组头指针int right = i - 1;//数组尾指针while(left < right){if(arr[left] != arr[right]){//不是回文结构return false;}left++;right--;}//是回文结构return true;}
};

思路2：反转链表

  1. 找链表的中间节点（快慢指针）
  2. 将中间节点之后的链表进行反转
  3. 从原链表的头和反转链表比较节点的值
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {public:ListNode* findMidNode(ListNode* phead){ListNode* slow = phead;ListNode* fast = phead;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* reverseList(ListNode* phead){ListNode* n1, *n2, *n3;n1 = NULL; n2 = phead, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;}bool chkPalindrome(ListNode* A) {// write code here//1.找中间节点ListNode* mid = findMidNode(A);//2.根据中间节点反转后面链表ListNode* right = reverseList(mid);//3.从原链表的头和反转链表比较节点的值ListNode* left = A;while(right){if(left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};

3.4.7 相交链表

点击链接做题

在这里插入图片描述

思路：

  1. 如何判断链表是否相交
  2. 找相交链表的起始节点
  1. 遍历两个链表，若尾结点相同，则链表一定相交。
  2. 两个链表节点个数相同：往后遍历，找到相交的位置
  3. 两个链表节点个数不同：
    1. 找两个链表的节点数差值
    2. 让长链表先走差值步
    3. 两个链表开始遍历，比较是否为同一个节点

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* l1 = headA;ListNode* l2 = headB;int sizeA = 0, sizeB = 0;//计算链表长度,保存在sizeA，sizeB里面while(l1){sizeA++;l1 = l1->next;}while(l2){sizeB++;l2 = l2->next;}//计算链表差值(绝对值)int gap = abs(sizeA - sizeB);//让长链表先走gap步ListNode* longList = headA;ListNode* shortList = headB;if(sizeA < sizeB){//说明sizeB链表更长一些,否则就不交换longList = headB;shortList = headA;}while(gap--){longList = longList->next;}//此时longlist指针和shortlist指针在同一起跑线//链表相交，链表不相交while(longList && shortList){if(longList == shortList){//链表相交return longList;}//继续往后走longList = longList->next;shortList = shortList->next;}//链表不相交return NULL;
}

3.4.8 环形链表I

点击链接做题

在这里插入图片描述

思路：快慢指针

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {//快慢指针ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}//两个指针始终没有相遇return false;
}
思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！

在这里插入图片描述

slow一次走1步，fast一次走2步，fast先进环，假设slow也走完入环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小1步

因此，在带环链表中慢指针走一步，快指针走两步最终一定会相遇。

思考2：快指针一次走3步，走4步，...n步行吗?

step1:

按照上面的分析，慢指针每次走一步，快指针每次走三步，此时快慢指针的最大距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小2步追击过程中fast和slow之间的距离变化：

在这里插入图片描述

分析:

  1. 如果N是偶数，第一轮就追上了

  2. 如果N是奇数，第一轮追不上，快追上，错过了，距离变成-1，即C-1，进入新的一轮追击

    a. C-1如果是偶数，那么下一轮就追上了

    b. C-1如果是奇数，那么就追不上，进入新的一轮追击

总结一下追不上的前提条件：N是奇数，C是偶数

step2：

在这里插入图片描述

假设：

环的周长为C，头结点到slow结点的长度为L，slow走一步，fast走三步，当slow指针入环后，slow和fast指针在环中开始进行追逐，假设此时fast指针已经绕环x周。

在追逐过程中，快慢指针相遇时所走的路径长度:

fast: L+xC+C-N

slow：L

由于慢指针走一步，快指针要走三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即：

3L = L + xC + C − N （化简前）

2L = (x + 1)C − N （化简后）

对上述公式继续分析：由于偶数乘以任何数都为偶数，因此2L一定为偶数，则可推导出可能得情况：

  • 情况1：偶数 = 偶数 - 偶数

  • 情况2：偶数 = 奇数 - 奇数

由step1中（1）得出的结论，如果N是偶数，则第一圈快慢指针就相遇了。

由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进行下一轮的追逐；当N是奇数，要满足以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数，满足（2）a中的结论，则快慢指针会相遇

因此， step1 中的 N是奇数，C是偶数不成立 ，既然不存在该情况，则快指针一次走3步最终一定也可以相遇。

快指针一次走4、5…步最终也会相遇，其证明方式同上。

提示：

虽然已经证明了快指针不论走多少步都可以满足在带环链表中相遇，但是在编写代码的时候会有额外的步骤引入，涉及到快慢指针的算法题中通常习惯使用慢指针走一步快指针走两步的方式。

3.4.9 环形链表II

点击链接做题

在这里插入图片描述

思路：快慢指针

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的未尾

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {//找环的相遇点//从头结点和相遇点开始遍历，每次都走一步ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//相遇即链表一定带环ListNode* pcur = head;while(pcur != slow){pcur = pcur->next;slow = slow->next;}return pcur;}}//链表不带环return NULL;
}

3.4.10 随机链表的复制

点击链接做题

在这里插入图片描述

思路：

浅拷贝：拷贝值

深拷贝：拷贝空间

  1. 在原链表的基础上继续复制链表
  2. 置random指针
  3. 复制链表和原链表断开

代码：

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/
typedef struct Node Node;
Node* buyNode(int x){Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}
void AddNode(Node* phead){Node* pcur = phead;while(pcur){Node* Next = pcur->next;//创建新结点，尾插到pcurNode* newnode = buyNode(pcur->val);//newnode是复制结点pcur->next = newnode;newnode->next = Next;pcur = Next;}
}struct Node* copyRandomList(struct Node* head) {if(head == NULL){return NULL;}//1.原链表上复制结点AddNode(head);//2.置randomNode* pcur = head;while(pcur){Node* copy = pcur->next;if(pcur->random != NULL){copy->random = pcur->random->next;}pcur = copy->next;}//3.断开链表//在copy的链表里面设置两个指针：newHead,newTail位于拷贝链表的头//pcur往后挪两个到newHead->next，newTail挪到pcur->nextpcur = head;//让pcur先回到头节点Node* newHead, *newTail;newHead = newTail = pcur->next;while(pcur->next->next){//如果pcur->next->next为空就说明结束了pcur = pcur->next->next;newTail->next = pcur->next;//让newTail->next指向copy链表的后一个元素newTail = newTail->next;//把newTail移到copy链表的后一个元素的位置}return newHead;//返回新链表newHead到newTail
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/3245563.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

几何相关计算

几何相关计算

目录 一、 判断两个矩形是否相交 二、判断两条线段是否相交 三、判断点是否在多边形内 四、垂足计算 五、贝塞尔曲线 六、坐标系 一、 判断两个矩形是否相交 当矩形1的最大值比矩形2的最小值都小&#xff0c;那矩形1和矩形2一定不相交&#xff0c;其他同理。 struct Po…
阅读更多...
ETL之DataX模板（数据同步）

ETL之DataX模板（数据同步）

今天跟大家分享数据同步datax的模板&#xff0c;小伙伴们简单直接借鉴使用。 还记得上一篇关于大数据DS调度工具的分享嘛&#xff1f; 主流大数据调度工具DolphinScheduler之数据ETL流程-CSDN博客 里面的核心就是采用了DATAX的数据同步原理。 1&#xff0c;什么是DataX Da…
阅读更多...
逻辑漏洞-垂直越权

逻辑漏洞-垂直越权

【实验介绍】 垂直越权&#xff1a;是不同级别之间或不同角色之间的越权。由于后台应用没有做权限控制&#xff0c;或仅仅在菜单、按钮上做了权限控制&#xff0c;导致恶意用户只要猜测其他管理页面的 URL 或者敏感的参数信息&#xff0c;就可以访问或控制其他角色拥有的数据或…
阅读更多...
使用工作日志 - 更快地恢复专注并理清思路

使用工作日志 - 更快地恢复专注并理清思路

原文&#xff1a;Charles Fval - 2024.07.12 你正在处理计算机科学中最复杂的问题&#xff1a;修复部署管道上的权限。这已经是你开始处理这个简单任务的第 4 天了。你的经理明确告诉你&#xff0c;你在这方面的表现远低于她对一个中期实习生的期望。你的同事们都尽量远离你&a…
阅读更多...
WebGoC题解(10) 171.(201706比赛)第8题：数列（series）

WebGoC题解(10) 171.(201706比赛)第8题：数列（series）

题目描述 小P昨天数学留了一道关于数列的作业&#xff1a; 数列的前几项是&#xff1a;50,51,53,56,60,65,...。要求找到规律&#xff0c;计算出前N项。 作为goc高手&#xff0c;小P设计了一个用图形表示这个数列的方案。具体的设计是&#xff1a; 把一周均匀分成N个角度&#…
阅读更多...
[C++]——同步异步日志系统（6）

[C++]——同步异步日志系统（6）

同步异步日志系统 一、日志器模块设计1.1 同步日志器模块设计1.1.1 局部日志器建造者模式设计1.1.2 同步日志器基本功能测试 1.2 异步日志器模块设计1.2.1 单缓冲区设计1.2.2 异步工作线程的设计&#xff08;双缓冲区思想&#xff09;1.2.3 异步日志器设计1.2.4 异步日志器建造…
阅读更多...
Python数据分析-植物生长数据分析（机器学习模型和神经网络模型）

Python数据分析-植物生长数据分析（机器学习模型和神经网络模型）

一、研究背景 植物生长受多种环境因素的影响&#xff0c;包括土壤类型、日照时间、浇水频率、肥料类型、温度和湿度等。这些因素不仅影响植物的生长速度和健康状况&#xff0c;还对植物在不同生长阶段的表现有显著影响。随着气候变化和环境污染问题的加剧&#xff0c;研究如何…
阅读更多...
Spring如何进行动态注册Bean

Spring如何进行动态注册Bean

在Spring框架中&#xff0c;Bean是应用程序的核心组成部分&#xff0c;而BeanDefinition则是这些Bean的元数据表示。随着应用程序的复杂性增加&#xff0c;我们可能需要更灵活地定义和注册Bean。Spring框架提供了几个扩展点&#xff0c;允许我们以编程方式影响Bean的创建和定义…
阅读更多...
【vulhub】FRISTILEAKS:1.3

【vulhub】FRISTILEAKS:1.3

目录 下载地址 1、信息收集获取ip获取端口目录扫描 2、漏洞利用3、提权反弹shell脚本检测脏牛提权 下载地址 FristiLeaks: 1.3 ~ VulnHub 1、信息收集 获取ip 打开靶机就可以看到Ip 192.168.8.23 获取端口 fscan扫一下 获取80端口 目录扫描 网站访问 192.168.8.23:80…
阅读更多...
内行人才知道的白酒术语

内行人才知道的白酒术语

&#x1f61c;宝子们&#xff0c;今天来给大家分享一些只有内行人懂的白酒术语&#xff0c;让你在酒桌上也能显得很专业&#xff01;&#x1f4aa; ⬆️基酒术语解释&#xff1a;所谓基酒就是最基础的酒&#xff0c;也叫原浆酒&#xff0c;是指成酒后不经过勾调的酒液。基酒度…
阅读更多...
烟雾监测与太阳能源：实验装置在其中的作用

烟雾监测与太阳能源：实验装置在其中的作用

太阳光在烟雾中的散射效应研究实验装置是一款模拟阳光透过烟雾环境的设备。此装置能帮助探究阳光在烟雾中的传播特性、散射特性及其对阳光的影响。 该装置主要包括光源单元、烟雾发生装置、光学组件、以及系统。光源单元负责产生类似于太阳光的光线&#xff0c;通常选用高亮度的…
阅读更多...
迈克尔的44岁：时间的感悟与人生的智慧

迈克尔的44岁：时间的感悟与人生的智慧

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
Ubuntu Desktop Docker 配置代理

Ubuntu Desktop Docker 配置代理

Ubuntu Desktop Docker 配置代理 主要解决 docker pull 拉取不了镜像问题. Docker Desktop 配置代理 这个比较简单, 直接在 Docker Desktop 里设置 Proxies, 示例如下: http://127.0.0.1:7890 Docker Engine 配置代理 1.Docker Engine 使用下面配置文件即可, root 用户可…
阅读更多...
动手学深度学习6.3 填充和步幅-笔记练习（PyTorch）

动手学深度学习6.3 填充和步幅-笔记练习（PyTorch）

以下内容为结合李沐老师的课程和教材补充的学习笔记&#xff0c;以及对课后练习的一些思考&#xff0c;自留回顾&#xff0c;也供同学之人交流参考。 本节课程地址&#xff1a;填充和步幅_哔哩哔哩_bilibili 代码实现_哔哩哔哩_bilibili 本节教材地址&#xff1a;6.3. 填充和…
阅读更多...
Linux下Qt程序打包

Linux下Qt程序打包

文章目录 一、前言二、linuxdeployqt下载安装三、Qt环境变量配置四、准备Qt可执行文件五、打包六、封装成deb安装包 一、前言 在Windows下进行Qt开发&#xff0c;软件开发好之后可以使用windeployqt进行打包&#xff0c;然后程序就可以移动到其它电脑上运行了 在Linux下同样可…
阅读更多...
浅析stm32启动文件

浅析stm32启动文件

浅析stm32启动文件 文章目录 浅析stm32启动文件1.什么是启动文件&#xff1f;2.启动文件的命名规则3.stm32芯片的命名规则 1.什么是启动文件&#xff1f; 我们来看gpt给出的答案&#xff1a; STM32的启动文件是一个关键的汇编语言源文件&#xff0c;它负责在微控制器上电或复位…
阅读更多...
开箱即用的AI！九州未来亓绚AI教培一体机全新发布

开箱即用的AI！九州未来亓绚AI教培一体机全新发布

以大模型、生成式人工智能为代表的人工智能技术在全球引起广泛关注&#xff0c;亦成为催生教育变革的重要力量。 中小学人工智能教育逐步推进&#xff0c;但实施过程中仍然面对诸多挑战。如何更广泛、高质量地开展中小学人工智能教育&#xff0c;成为当下我国教育改革创新的重…
阅读更多...
CentOS7 虚谷数据库 单机版部署

CentOS7 虚谷数据库 单机版部署

单机版最低配置&#xff1a; 安装环境配置 1.CPU设置 关闭 CPU 超线程 查看当前CPU超线程状态&#xff1a; cat /sys/devices/system/cpu/smt/active 如果是0&#xff0c;表示超线程已关闭&#xff1b;返回值是1&#xff0c;表示超线程已开启。 切换超线程状态&#xff1a; &a…
阅读更多...
景区客流统计系统提升服务精准度

景区客流统计系统提升服务精准度

在当今旅游业蓬勃发展的时代&#xff0c;景区面临着越来越多的挑战和机遇。如何在保障游客良好体验的同时&#xff0c;实现景区的高效管理和可持续发展&#xff0c;成为了摆在景区管理者面前的重要课题。景区客流统计系统的出现&#xff0c;为解决这一问题提供了有力的支持&…
阅读更多...
vscode 打开远程bug vscode Failed to parse remote port from server output

vscode 打开远程bug vscode Failed to parse remote port from server output

vscode 打开远程bug vscode Failed to parse remote port from server output 原因如图&#xff1a; 解决&#xff1a;
阅读更多...
最新文章

Copyright @ 2022~2023