数组、链表专题

发布时间：2024年01月12日

线性表

定义如下：

线性表是指零个或者多个数据元素的有限序列；
线性表是一个序列，也就是元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其它每个元素都有且只有一个前驱和后继。
线性表有两种存储结构，一种是顺序存储[数组]，一种是链式存储[链表]。
栈与队列都是操作受限的线性表，这两个将会在下一篇文章介绍，这篇文章先介绍数组和链表。

数组

为什么数组从0开始编号而不是从1开始

数组是一种线性表数据结构。用一组连续的内存空间，存储一组具有相同类型的数据。
正是因为数组用连续的内存空间存储相同类型的数据，才能够实现随机访问，相应的弊端就是插入，删除时为了保证数据的连续性需要做大量的数据迁移工作。

假设数组的长度为n，现在需要将一个数据插入到数组的第k个位置。为了把第k个位置腾出来给新数据使用，需要将k~n这部分的元素都顺序地向后挪一位，插入操作的时间复杂度为多少?

如果在数组的末尾插入元素，不需要移动数据，时间复杂度为O(1)。
在数组的开头插入元素，所有的数据都需要依次向后移动一位，最坏的时间复杂度为O(n)。由于在每个位置插入元素的概率是一样的，平均时间复杂度为(1+2+3…+n)/n = O(n)

如果数组中的数据是有序的，在某个位置插入一个新的元素，必须迁移插入位置之后的元素。但是如果数组中存储的数据没有任何规律只是被当作一个存储数据的集合，在这种情况下，将元素插入到第k个位置，为了避免大规模的数据迁移，可以直接将第k个位置的数据迁移到末尾，把新的元素直接放入第k个位置。[基于数据交换的思想]
在这里插入图片描述
若删除数组中第k个位置的元素，时间复杂度为多少？

删除数组末尾的数据，最好情况时间复杂度为O(1)
删除数组开头的数据，最坏情况时间复杂度为O(n)
平均时间复杂度为(1+2+3…+n)/n=O(n)

实际上，在某些特殊的场景下，并不一定非要保持数组中数据的连续性。如果将多次删除操作集中在一起执行，删除的效率就会提高。[写到这里想到mysql-DML中的delete操作，delete操作并不是真正的将操作的记录删除，而是对这条记录打上一个"delete flag"的标识，标记这个记录已经被删除这条记录所占用的内存空间可以被复用，这样一来可以节省开销]

可以先记录已被删除的数据，每次删除操作并不迁移数据，当数组没有更多存储空间时，再执行真正的删除操作，大大减少删除操作导致的数据迁移。

数组VS容器

针对数组类型很多语言提供了容器类，比如C++STL中的vector，Java中的ArrayList，go中的slice。
容器最大的优势就是将很多数组操作的细节封装起来，并且可以支持动态扩容。[扩容操作涉及的内存申请和数据迁移是比较耗时的]

什么时候适合用数组，什么时候适合用容器？

如果数据大小事先已知，并且对数据的操作非常简单，用不到容器提供的大部分方法可以使用数组
表示多维数组时用数组更加直观，datatype data[][]；用容器则表示为vector<vector<datatype>> data
对于业务开发直接使用容器，省时省力。如果是做一些非常底层的开发比如开发网络框架，性能需要做到极致，这个时候数组优于容器。

** 为什么数组下标从0开始**
从数组存储的内存模型上看，“下标”最确切的定义应该是偏移(offset)。如果用a表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，a[k]就表示偏移k个type_size的位置，计算a[k]的内存地址只需要用如下的公式

a[k]_address = base_address + k*type_size

但是，如果数组从1开始计数，计算公式如下:

a[k]_address = base_address + (k-1)*type_size

对比两个公式，可以发现从1开始编号，每次随机访问数组都多了一次减法运算，对CPU来说就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素是非常基础的编程操作，效率的优化就要尽可能做到极致。为了减少一次减法操作，数组选择从0开始编号，而不是从1开始。

最主要的原因可能是历史原因。
C语言设计者用0开始计数数组下标，之后的Java，JavaScript等高级语言效仿了C语言，因此继续沿用从0开始计数的习惯。实际上很多语言中数组也并不是从0开始计数，比如Matlab从1开始计数，Python还支持负数下标。

二维数组的寻址公式

a[i][j]_address = base_address+(i*n+j)*type_size
0<=i<=m,0<=j<=n

接下来看一下有关“数组”的算法题

算法题

二分查找

题目

给定一个n个元素有序的(升序)整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在则返回下标，否则返回-1；
其中n在[1,10000]之间，nums的每个元素都将在[-9999,9999]之间

输入

首先输入一个正整数n和一个正整数target分别表示nums的元素个数和要找的目标值，另起一行输入各个元素。

输出

目标值存在输出下标，不存在输出-1

测试样例

样例1
6 9
-1 0 3 5 9 12
4
样例2
6 2
-1 0 3 5 9 12
-1

思路：

暴力查找。顺序遍历数组对比每个位置上的元素，时间复杂度为O(n)空间复杂度为O(1)。
二分查找。所给定的nums本身就是有序的所以可以使用二分查找时间复杂度为O(logn)空间复杂度为O(1)。二分查找区间又可以分为"左闭右闭"和"左闭右开"两种方式

采用"二分查找"进行编程

#include<iostream>
#include<vector>
using namespace std;
int my_binary_search(const vector<int>&,int);
int main(){
        int n,target;cin>>n>>target;
        vector<int>nums(n,0);
        for(int i=0;i<n;++i) cin>>nums[i];
        cout<<my_binary_search(nums,target)<<endl;
        return 0;
}
//这里使用的是容器所以不需要传递nums中的元素个数n
//如果这里使用的是数组，需要传递nums的长度n
int my_binary_search(const vector<int>&nums,int num){
        int n = nums.size();
        //int l=0,r=n-1;//左右边界[左,右]
        //while(l<=r){
        //      int mid = l+((r-l)>>1);
        //      if(nums[mid]>num) r=mid-1;
        //      else if(nums[mid]<num) l=mid+1;
        //      else return mid;
        //}
        int l=0,r=n;//[左,右)
        while(l<r){
                int mid = l+((r-l)>>1);
                if(nums[mid]>num) r=mid;
                else if(nums[mid]<num) l=mid+1;
                else return mid;
        }
        return -1;
}

package main

import "fmt"


func main(){
        var n,target int
        fmt.Scan(&n,&target);
        nums:=make([]int,n)
        for i:=0;i<n;i++{
                fmt.Scan(&nums[i])
        }
        var my_bs func()int
        l,r:=0,n-1
        my_bs=func()int{
                for l<=r{
                //算术运算符的优先级高于位移运算符
                        mid:=l+((r-l)>>1)
                        if nums[mid]>target{
                                r=mid-1
                        }else if nums[mid]<target{
                                l=mid+1
                        }else {
                                return mid
                        }
                }
                return -1
        }
        fmt.Println(my_bs())
}

移除元素

题目

给定一个数组nums和一个值val，原地移除所有数值等于val的元素，返回移除后数组的长度和数组的各个元素
元素的顺序可以改变，必须是原地修改，不需要考虑超出新长度后面的元素
0<=nums.length<=100
0<=nums[i]<=50
0<=val<=100

输入

输入n和val表示数组的长度和删除的目标值，紧接着另起一行输入n个数组的元素。

输出

输出移除后数组的长度，另起一行输出移除后数组的各个元素

测试样例

样例1
4 3
3 2 2 3
2
2 2
样例2
8 2
5
0 1 3 0 4

思路：

最直观的想法就是，把不满足要求的数值从数组中拿出去，为了避免大量数据的迁移，我们可以采用上文提到的"标记法"。
使用双指针，一个指向"下一个满足要求的元素的存储位置"，一个用来遍历数组，遇到不满足要求的元素直接忽略[“标记”]就好。
时间复杂度为O(n)空间复杂度为O(1)

#include<iostream>
#include<vector>
using namespace std;

int main(){
        int n,val;
        cin>>n>>val;
        vector<int>nums(n);
        for(int i=0;i<n;++i) cin>>nums[i];
        //remove num
        int l=0;
        for(int r=0;r<n;++r) if(nums[r]!=val) nums[l++]=nums[r];
        //the len of new nums is l
        cout<<l<<endl;
        for(int i=0;i<l;++i) {
                if(i!=0) cout<<" ";
                cout<<nums[i];
        }
        cout<<endl;
        return 0;
}

package main

import "fmt"

func main(){
        var n,val int
        fmt.Scan(&n,&val)
        nums:=make([]int,n)
        for i:=0;i<n;i++{
                fmt.Scan(&nums[i])
        }
        //remove num
        l:=0
        for r:=0;r<n;r++{
                if nums[r]!=val{
                        nums[l]=nums[r]
                        l++
                }
        }
        fmt.Println(l)
        for i:=0;i<l;i++{
                if i!=0{
                        fmt.Print(" ")
                }
                fmt.Print(nums[i])
        }
}

有序数组的平方

题目

给定一个按照非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求新数组也按照非递减的顺序排序
1<=nums.length<= $10^4$
- $10^4$ <=nums[i]<= $10^4$

输入

输入n表示数组的长度，另起一行输入n个数组元素

输出

按照非递减顺序排序的平方数组

测试样例

样例1
5
-4 -1 0 3 10
0 1 9 16 100
样例2
5
-7 -3 2 3 11
4 9 9 49 121

思路：

先不考虑"平方后的数组按照非递减顺序排序"这个要求，只需要遍历原数组并将其平方即可。现在依然可以按照上述的思路，为了保证非递减的顺序可以在平方之后排序。遍历数组的时间复杂度为O(n)，排序最快的快速排序的时间复杂度为O(nlogn)，总时间复杂度为O(nlogn)，空间复杂度为O(logn);

有没有更简便一点的方法呢？在遍历平方的同时进行排序。

数组的元素的情况无非就是三种：全是正整数，全是负整数，既有正整数又有负整数。正整数和负整数的情况很简单。对于全是正整数的情况，遍历平方即可；对于全是负整数的情况，遍历平方逆转即可。
对于既有负整数又有正整数的情况，对于负数，排在前面的反而小但是平方值大，对于正数排在后面的大平方值也大。可以参照"对于两个有序序列的归并排序"，不过这里是从大到小进行排序；可以使用双指针，一个指针指向数组的开头[有可能指向的是负整数也有可能是正整数]，另一个指针指向数组的结尾[有可能指向的是负整数也有可能是正整数]。比较两个指针指向的数值平方，谁比较大将其加入辅助数组。[由于选择的是较大的值，所以从辅助数组的末尾开始向头部添加平方值]

#include<iostream>
#include<vector>
using namespace std;

int main(){
        int n;cin>>n;
        vector<int>nums(n);
        for(int i=0;i<n;++i) cin>>nums[i];
        vector<int>ans(n);
        int in=n-1,l=0,r=n-1;
        while(l<=r){
                int n1=nums[l]*nums[l],n2=nums[r]*nums[r];
                if(n1>n2) {
                        ans[in--]=n1;
                        ++l;
                }else{
                        ans[in--]=n2;
                        --r;
                }
        }
        for(const int&a:ans) {
                cout<<a<<" ";
        }
        return 0;
}

package main

import "fmt"

func main(){
        var n int
        fmt.Scan(&n)
        nums,ans:=make([]int,n),make([]int,n)
        for i:=0;i<n;i++{
                fmt.Scan(&nums[i])
        }
        in,l,r:=n-1,0,n-1
        for l<=r{
                n1:=nums[l]*nums[l]
                n2:=nums[r]*nums[r]
                if n1>n2{
                        ans[in]=n1
                        l++
                }else{
                        ans[in]=n2
                        r--
                }
                in--
        }
        for _,num:=range ans{
                fmt.Print(num," ")
        }
}

长度最小的子数组

题目

给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于target的长度最小的连续子数组，返回其长度和连续数组。不存在符合条件的子数组返回0

输入

输入正整数n和target表示数组的长度和目标总和，另起一行输入n个数组元素

输出

满足条件的数组长度和对应的数组元素

测试样例

样例1
6 7
2 3 1 2 4 3
2
4 3
样例2
3 4
1 4 4
1
4
样例3
8 11
1 1 1 1 1 1 1 1
0

思路：

暴力法。双层for循环遍历数组，一层for循环指向子数组的起始位置，二层for循环指向子数组的末尾位置；时间复杂度为O( $n^2$ )。

如何对上述的方法进行优化呢？上述的双层for循环做了很多的重复工作，一个元素可能出现在某个子数组的开头或者中间或者末尾导致这个元素被计算了很多遍。有没有一种方法，每个元素只遍历一遍只计算一遍。

滑动窗口，刚开始的时候窗口右边界向右移动扩大窗口直到窗口内的元素和大于等于target，此时记录窗口大小和窗口内的元素，向右移动窗口左边界缩小窗口直到窗口内元素和小于target。

#include<iostream>
#include<vector>
using namespace std;

int main(){
        int n,target;
        cin>>n>>target;
        vector<int>nums(n);
        for(int i=0;i<n;++i) cin>>nums[i];
        int minlen=n+1,al=-1,ar=-1;
        int sum=0,l=0;
        for(int r=0;r<n;++r){
                sum+=nums[r];
                while(sum>=target){
                        int len=r-l+1;
                        if(len<minlen){
                                minlen=len;
                                al=l;
                                ar=r;
                        }
                        sum-=nums[l];
                        l++;
                }
        }
        if(minlen==n+1) cout<<0<<endl;
        else {
                cout<<minlen<<endl;
                for(int i=al;i<=ar;++i) cout<<nums[i]<<" ";
        }
}

package main

import "fmt"

func main(){
        var n,target int
        fmt.Scan(&n,&target)
        nums:=make([]int,n)
        for i:=0;i<n;i++ {
                fmt.Scan(&nums[i])
        }
        minlen,al,ar:=n+1,-1,-1
        sum,l:=0,0
        for r:=0;r<n;r++{
                sum+=nums[r]
                for sum>=target{
                        len:=r-l+1
                        if len<minlen{
                                minlen=len
                                al,ar=l,r
                        }
                        sum-=nums[l]
                        l++
                }
        }
        if minlen==n+1{
                fmt.Println(0)
        }else{
                fmt.Println(minlen)
                for i:=al;i<=ar;i++ {
                        fmt.Print(nums[i]," ")
                }
        }
}

螺旋矩阵

题目

给定一个正整数n，生成一个包含1~ $n^2$ 所有元素，且元素按照顺时针顺序螺旋排列的n*n正方形矩阵

输入

输入正整数n

输出

输出n*n的矩阵包含1~ $n^2$ 的所有元素，且元素按照顺时针螺旋排列

测试样例

样例1
1
1
样例2
3
1 2 3
8 9 4
7 6 5

思路：

先填充行再填充列，但是行列的交叉处又该如何考虑？如果将其规划给行就不要在列中考虑，如果将其规划给列就不要在行中考虑，不然的话既在行中考虑又在列中考虑很容易混乱。
采用左闭右闭[也就是在行中考虑]或者左闭右开[在列中考虑]都可以。但是左闭右开更简单一点，以下程序采用左闭右开的方式完成。除了考虑行列的交叉处还要考虑n是偶数还是奇数，如果是奇数正中间的那个位置需要单独考虑。

#include<iostream>
#include<vector>
using namespace std;

int main(){
        int n;cin>>n;
        //int matrix[n][n]
        vector<vector<int>> matrix(n,vector<int>(n,0));
        int num=1;//from 1 to n^2

        for(int c=0;c<n/2;++c){
                //c表示每一圈的起始位置，同时也表示填充的圈数
                int row=c,col=c;
                //hang[left,right)
                for(;col<n-c-1;++col) matrix[row][col]=num++;

                //lie
                for(;row<n-c-1;++row) matrix[row][col]=num++;

                //hang
                for(;col>c;--col) matrix[row][col]=num++;

                //lie
                for(;row>c;--row) matrix[row][col]=num++;
        }

        //n is odd?
        if(n&1) matrix[n/2][n/2]=num;

        for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                        if(j!=0) cout<<" ";
                        cout<<matrix[i][j];
                }
                cout<<endl;
        }
}

package main

import "fmt"

func main(){
	var n int
	fmt.Scan(&n)
	num:=1
	matrix:=make([][]int,n)
	for i:=0;i<n;i++{
		matrix[i]=make([]int,n)
	}

	for c:=0;c<n/2;c++{
		row,col:=c,c

		for ;col<n-c-1;col++ {
			matrix[row][col]=num
			num++
		}

		for ;row<n-c-1;row++{
			matrix[row][col]=num
			num++
		}

		for ;col>c;col--{
			matrix[row][col]=num
			num++
		}

		for ;row>c;row--{
			matrix[row][col]=num
			num++
		}
	}
	if n&1==1 {matrix[n/2][n/2]=num}

	for i:=0;i<n;i++{
		for j:=0;j<n;j++{
			if j!=0 {
				fmt.Print(" ")
			}
			fmt.Print(matrix[i][j])
		}
		fmt.Println()
	}
}

链表

数组存储元素需要连续的内存存储空间。而链表不需要，它通过"指针"将一组零散的内存块串联起来使用，这些内存块称为链表的"结点"，为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上结点的地址。根据记录的结点不同，又分为不同的链表。

链表结构

单链表

每个结点除了存储数据之外，只存储下一个结点的地址[next后继指针]
在这里插入图片描述

从图上可以发现有两个特殊的结点，分别是第一个结点和最后一个结点。习惯性地把第一个结点叫做头结点，把最后一个结点叫做尾结点。头结点用来记录链表的基地址，有了头结点就可以遍历整个链表。尾结点指向的不是下一个结点而是指向一个空地址NULL，表示这是链表上最后一个结点。
在讨论数组的时候分析过，由于数组是连续存储的所以插入和删除都需要进行大量的元素迁移操作时间复杂度为O(n)。而对于链表是通过指针将结点进行串联的所以只需要修改相邻结点的指针指向时间复杂度为O(1)，但是对应的弊端就是不能够根据下标随机访问元素，需要从头遍历找到目标元素。

在这里插入图片描述

循环链表

循环链表是一种特殊的单链表，与单链表唯一的区别就在于尾结点指向的不是空地址NULL，而是第一个结点头结点，形成一个环状的结构。
在这里插入图片描述
循环链表的优点是从链尾到链头比较方便。

双向链表

每个结点除了存储数据之外，还存储上一个结点[prev前驱指针]和下一个结点的地址[后继指针]。
在这里插入图片描述
从上图可以看出，双向链表相比于单链表多了一个额外的存储空间存储前驱结点的地址。虽然比较浪费空间但是可以支持双向遍历，即从某个结点开始既可以往前走也可以往后走比较灵活。从结构上看:双向链表可以支持O(1)时间复杂度的情况下找到前驱结点，使双向链表在某些情况下比单链表的删除，插入更高效。

在实际的软件开发中，从链表中删除一个数据有以下两种情况:

删除结点中"值等于某个给定值"的结点
删除给定指针指向的结点
对于第一种情况，不论是单链表还是双向链表，为了查找值等于给定值的结点，都需要从头结点开始对比每一个结点直到找到目标结点[对于单链表来说找到目标值结点的前驱结点，对于双向链表来说找到目标值结点的前驱结点和目标值结点都可以]，然后才能通过修改相邻结点的指针删除具有目标值的结点。虽然单纯的删除操作的时间复杂度为O(1)，但是遍历查找的时间为O(n)，整体的时间复杂度为O(n)。
对于第二种情况，已经找到了要删除的目标结点。但是删除一个结点需要先找到目标结点的前驱结点，对于单链表由于只有后继指针所以需要从头结点开始找到目标结点的前驱结点时间复杂度为O(n)，双向链表由于存有结点的前驱指针故找到前驱结点的时间复杂度为O(1)。对于第二种情况，使用双链表更高效。

双向循环链表

双向循环链表就是将双向链表和循环链表相结合，结构如下
在这里插入图片描述

链表代码编写的小技巧

理解指针或引用的含义

不管是指针还是引用存储的都是所指对象的内存地址，通过这个地址就可以找到所指的对象

警惕指针丢失和内存泄露

插入结点的时候要注意操作的顺序，比如要在a,b两个结点之间插入x结点，如果按如下顺序执行

a->next=x;
x->next=a->next;

就会发生错误，在第一步操作之后a结点的下一个指向的就变成了x，在执行第二步时，x指向了自己。就会导致链表从x结点开始发生了中断，没有及时释放内存的话会造成内存泄漏。

删除结点时，要记得手动释放内存空间，否则会出现内存泄露的问题。[对于自动管理内存的语言不需要考虑]

利用哨兵简化实现难度

首先回顾一下单链表的插入和删除操作。如果在结点p后面插入一个新的结点，只需要下面两行代码即可

newnode->next = p->next
p->next = newnode

但是，要向一个空链表中插入第一个结点，需要进行一些特殊的处理，其中head表示链表的头结点。

if(head==NULL) {head = newnode;}

从上述代码可以发现，对与单链表的插入操作，第一个结点和其它结点的插入逻辑不一致。接下来看看删除操作。

如果要删除结点p的后继结点，只需要一行代码即可

p->next = p->next->next;

但是，如果要删除链表的最后一个结点，和插入操作一样也需要一些特殊处理。

if(head==p) head=NULL;

从上面的分析可以看出，针对链表的插入和删除操作，插入第一个结点和删除第一个结点需要进行一些特殊的处理，这让代码实现起来很繁琐不简便。

可以通过设置哨兵解决上述的问题。
引入哨兵结点，不论链表是否为空，head指针都会指向这个哨兵结点。通常把带有哨兵结点的链表叫做带头链表，没有哨兵结点的链表叫做不带头链表。这样一来所有的操作都得到了统一。

在这里插入图片描述

重点留意边界条件处理

链表代码编写，需要考虑以下三个边界

如果链表为空，代码能否正常工作
如果链表只包含一个结点，代码能否正常工作
如果链表只包含两个结点，代码能否正常工作
代码逻辑在处理头结点和尾结点的时候，能否正常工作

算法题

两个有序链表的合并

题目

将两个升序链表合并为一个新的升序链表并返回。

输入

输入两个整数m,n分别表示两个链表的元素个数。另起两行分别输入第一个和第二个链表中的元素值

输出

输出合并之后链表中的元素

测试样例

样例1
3 3
1 2 4
1 3 4
1 1 2 3 4 4
样例2
0 0
样例3
0 1
0
0

思路:

双指针。与"合并两个有序数组"的思路是一致的。使用两个指针分别指向第一个和第二个链表，比较两个指针指向的结点的数值，谁比较小就将其加入新链表，并将指针向后移动。

#include<iostream>
using namespace std;

//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
void remove(listnode*,int);
int main(){
	//head 
	listnode *head1 = new listnode();
	listnode *head2 = new listnode();
	listnode *mv1 = head1;
	listnode *mv2 = head2;
	int m,n,num;cin>>m>>n;
	for(int i=0;i<m;++i){
		cin>>num;
		listnode *node = new listnode(num);
		node->next = mv1->next;
		mv1->next=node;
		mv1=node;
	}
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		node->next = mv2->next;
		mv2->next=node;
		mv2=node;
	}

	//merge
	listnode *head = new listnode();
	listnode *mv=head;
	mv1=head1->next,mv2=head2->next;
	while(mv1&&mv2){
		if(mv1->val<mv2->val){
			mv->next = mv1;
			mv1=mv1->next;
		}else{
			mv->next=mv2;
			mv2=mv2->next;
		}
		mv=mv->next;
	}
	if(mv1) mv->next=mv1;
	else if(mv2) mv->next=mv2;

	//print mergelist
	mv=head->next;
	while(mv) {
		cout<<mv->val<<" ";
		mv=mv->next;
	}
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	head1:=newlistnode()
	head2:=newlistnode()
	mv1:=head1
	mv2:=head2

	var m,n,num int
	fmt.Scan(&m,&n)
	for i:=0;i<m;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		node.next=mv1.next
		mv1.next=node
		mv1=node
	}
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		node.next=mv2.next
		mv2.next=node
		mv2=node
	}
	//merge list
	head:=newlistnode()
	mv:=head
	mv1,mv2=head1.next,head2.next
	for mv1!=nil&&mv2!=nil{
		if mv1.val<mv2.val{
			mv.next=mv1
			mv1=mv1.next
		}else{
			mv.next=mv2
			mv2=mv2.next
		}
		mv=mv.next
	}
	if mv1!=nil{
		mv.next=mv1
	}else if mv2!=nil{
		mv.next=mv2
	}
	//print list 
	mv=head.next
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
}

移除链表元素

题目

用链表存储一些整数，给定一个整数val，删除链表中结点值等于给定数值val的所有结点，并输出留下的数据值。
1<=node.val<=50
0<=val<=50

输入

输入整数n和val，分别表示元素的个数和删除的目标值。另起一行输入n个整数值

输出

分别输出删除特定值之前和删除特定值之后留下的数据值

测试样例

样例1
7 6
1 2 6 3 4 5 6
1 2 6 3 4 5 6
1 2 3 4 5
样例2
0 1
样例3
4 7
7 7 7 7
7 7 7 7

思路：

通过上述对链表的分析，为了统一并简化操作可以引入"哨兵结点"[这样就不用特殊处理头尾结点]。为了删除满足条件的结点需要先找到目标结点的前驱结点，所以在遍历的过程中需要有额外的变量存储结点的前驱结点

#include<iostream>
using namespace std;

//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
void remove(listnode*,int);
int main(){
	//head 
	listnode *head = new listnode();
	listnode *mv = head;
	int n,val,num;cin>>n>>val;
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		node->next = mv->next;
		mv->next=node;
		mv=node;
	}
	//print list before remove
	mv=head->next;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}
	cout<<endl;

	remove(head,val);

	//print list after remove
	mv=head->next;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}

	//delete node
	mv=head;
	while(mv) {delete mv;mv=mv->next;}
	return 0;
}

void remove(listnode *head,int val){
	listnode *mv=head;
	while(mv->next){
		if(mv->next->val==val) {
			listnode *te=mv->next;
			mv->next = te->next;
			te->next=nullptr;
			delete te;
		}else {
			mv=mv->next;
		}
	}
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	head:=newlistnode()
	mv:=head

	var n,val,num int
	fmt.Scan(&n,&val)
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		node.next=mv.next
		mv.next=node
		mv=node
	}

	//print list before remove
	mv=head.next
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
	fmt.Println()

	remove(head,val)
	//print list after remove
	mv=head.next
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
}


func remove(head *listnode,val int){
	mv:=head
	for mv.next!=nil{
		if mv.next.val==val{
			te:=mv.next
			mv.next=te.next
			te.next=nil
		}else {
			mv=mv.next
		}
	}
}

反转链表

题目

反转给定的链表

输入

输入一个整数n表示链表的元素个数，另起一行输入n个元素

输出

输出反转前后的链表元素值

测试样例

样例1
5
1 2 3 4 5
1 2 3 4 5
5 4 3 2 1
样例2
2
1 2
1 2
2 1
样例3
0

思路:

站在上帝视角看这道题，发现这不是很简单嘛[其实一点也不简单]，直接将链表的各个结点的指针指向反过来不就好了，于是很快就写出了代码，但是运行时发现出现了错误。
本质上是对的，就是将链表的各个结点的指针反过来，从指向下一个结点变为指向上一个结点，但是将一个结点的指针指向由下一个结点变为上一个结点时链表发生了断裂，所以关键的一步就是需要保存发生变化之前结点的下一个结点以及结点本身。可以用迭代[额外定义变量进行存储]或者递归[递归栈进行存储]来做。

迭代

#include<iostream>
using namespace std;


//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
listnode* reverse(listnode*);
listnode* reverse1(listnode*);
int main(){
	//head
	listnode *head=nullptr,*mv=nullptr;
	int n,num;cin>>n;
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		if(head==nullptr){ head=node;}
		else{
			node->next = mv->next;

			mv->next=node;
		}
		mv=node;
	}
	//print list before reserve
	mv=head;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}
	cout<<endl;

	listnode *newhead = reverse(head);

	//print list after reserve
	mv=newhead;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}

	//delete node
	mv=newhead;
	while(mv) {delete mv;mv=mv->next;}
	return 0;
}
listnode* reverse(listnode *head){
	//diedai
	listnode *mv=head,*pre=nullptr;
	while(mv->next){
		listnode *nextnode = mv->next;

		mv->next=pre;
		pre=mv;
		mv=nextnode;
	}
	mv->next = pre;
	return mv;
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	var head,mv *listnode

	var n,num int
	fmt.Scan(&n)
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		if head==nil{
			head=node
		}else{
			node.next=mv.next
			mv.next=node
		}
		mv=node
	}

	//print list before reverse
	mv=head
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
	fmt.Println()
	newhead:=reverse1(head)
	
	//print list after reverse
	mv=newhead
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
}

func reverse(head *listnode)*listnode{
	//deidai
	var pre *listnode
	for head.next!=nil{
		nextnode:=head.next

		head.next=pre
		pre=head
		head=nextnode
	}
	head.next=pre
	return head
}

递归

listnode* reverse1(listnode*head){
	if(!head || !head->next) return head;

	listnode *newhead = reverse1(head->next);
	head->next->next = head;
	head->next=nullptr;

	return newhead;
}

func reverse1(node *listnode)*listnode{
	if node==nil || node.next==nil{
		return node
	}

	head:=reverse(node.next)

	node.next.next=node
	node.next=nil

	return head
}

两两交换链表中的结点

题目

两两交换链表中相邻的结点，并返回交换之后链表的头结点。[只能进行结点交换，不能修改结点的内部值]
链表中结点的数目在范围[0,100]内
0<=node.val<=100

/输入

输入一个整数n表示链表的元素个数，另起一行输入n个元素

输出

两两交换前后的链表元素

测试样例

样例1
4
1 2 3 4
1 2 3 4
2 1 4 3
样例2
0
样例3
1
1
1

思路:

做完"反转链表"之后，你会发现这道题目相比与反转链表来说多了一个步骤:组间反转，两个结点为一组，组内的反转就是反转链表只不过结点数目变为了两个，组内反转之外还要进行组间反转
更多解法可以参考https://lyl0724.github.io/2020/01/25/1/

#include<iostream>
using namespace std;


//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
listnode* swap(listnode*);
listnode* swap1(listnode*);
int main(){
	//head
	listnode *head=nullptr,*mv=nullptr;
	int n,num;cin>>n;
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		if(head==nullptr) head=node;
		else{
			node->next = mv->next;
			mv->next=node;
		}
		mv=node;
	}
	//print list before swap
	mv=head;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}
	cout<<endl;

	listnode *newhead = swap(head);

	//print list after swap
	mv=newhead;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}

	//delete node
	mv=newhead;
	while(mv) {delete mv;mv=mv->next;}
	return 0;
}

listnode* swap(listnode *head){
	if(!head || !head->next) return head;
	listnode *newhead = head->next;
	//diedai
	while(head&&head->next){
		listnode *node=head->next->next;

		head->next->next=head;
		if(node&&node->next) head->next=node->next;
		else head->next = node;
		head=node;
	}

	 
	return newhead;
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	var head,mv *listnode

	var n,num int
	fmt.Scan(&n)
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		if head==nil{
			head=node
		}else{
			node.next=mv.next
			mv.next=node
		}
		mv=node
	}

	//print list before swap
	mv=head
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
	fmt.Println()

	newhead:=swap(head)
	//print list after swap
	mv=newhead
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
}

func swap(head *listnode)*listnode{
	if head==nil || head.next==nil {return head}
	newhead:=head.next
	for head!=nil&&head.next!=nil{
		node:=head.next.next
		head.next.next=head
		if node!=nil&&node.next!=nil {
			head.next=node.next
		}else {
			head.next=node
		}
		head=node
	}
	return newhead
}

删除链表的倒数第N个结点

题目

删除链表中倒数第N个结点

输入

输入整数m和n分别表示链表的元素个数和删除的结点位置[倒数]，另起一行输入m个链表元素

输出

输出删除倒数第n个结点前后，链表中的元素

测试样例

样例1
5 2
1 2 3 4 5
1 2 3 4 5
1 2 3 5
样例2
1 1
1
1
样例2
2 1
1 2
1 2
1

思路:

最容易想到的方法就是：首先从头到尾遍历链表统计链表中的元素个数假设是sum，若想要找到倒数第n个结点，只需要正向遍历到第sum-n[目标结点的前一个结点，因为删除操作需要知道前一个结点]个结点即可，此方法需要遍历两遍链表时间复杂度为O(n)空间复杂度为O(1)。
为了统一操作，可以使用"哨兵结点"进行优化。
有没有可以优化的地方呢？或者换一种说法"可以不可以只需要遍历一遍链表"就可以找到目标结点的前一个结点？先假设有一个长度固定的道路，有两个人A|B站在道路的两端向彼此靠近，由于道路的长度是固定的，A走的路程多对应的B走的路程就少。依据上述的思想，我们可以设置两个指针一个走得快一个走得慢，fast指针先向前走n步，之后slow\fast一起向前直到fast指针到达链表的末尾，此时slow指针指向的就是倒数第n个结点的前一个结点。

#include<iostream>
using namespace std;


//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
int main(){
	//head
	listnode *head=new listnode();
	listnode *mv=head;
	int m,n,num;cin>>m>>n;
	for(int i=0;i<m;++i){
		cin>>num;
		listnode *node = new listnode(num);
		node->next = mv->next;
		mv->next=node;
		mv=node;
	}
	//print list before delete
	mv=head->next;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}
	cout<<endl;
	
	{
		//delete node
		listnode *slow=head,*fast=head;
		while(n--) fast=fast->next;
		while(fast->next){
			fast=fast->next;
			slow=slow->next;
		}

		listnode *te = slow->next;
		slow->next = te->next;
		te->next=nullptr;
		delete te;



	}


	//print list after delete
	mv=head->next;
	while(mv) {cout<<mv->val<<" ";mv=mv->next;}

	//delete node
	mv=head;
	while(mv) {delete mv;mv=mv->next;}
	return 0;
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	head:=newlistnode()
	mv:=head

	var m,n,num int
	fmt.Scan(&m,&n)
	for i:=0;i<m;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		node.next=mv.next
		mv.next=node
		mv=node
	}

	//print list before delete
	mv=head.next
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
	fmt.Println()

	{
		//delete node
		fast,slow:=head,head
		for n>0{
			fast=fast.next
			n--
		}
		for fast.next!=nil{
			fast=fast.next
			slow=slow.next
		}

		slow.next = slow.next.next
	}

	//print list after delete
	mv=head.next
	for mv!=nil {
		fmt.Print(mv.val," ")
		mv=mv.next
	}
}

回文链表

题目

判断一个链表是否是回文链表

输入

输入一个整数n表示链表的元素个数，另起一行输入n个元素表示链表各结点的数值。

输出

若链表是回文链表则输出"YES"，否则输出"NO"

测试样例

样例1
6
1 2 3 3 2 1
YES
样例2
2
1 2
NO

思路:

对于回文串或者回文数组的判断是非常简单的利用双指针即可，但是由于链表不支持随机访问所以没办法利用双指针，但是可以先遍历一遍链表将数据值存储在字符串或者数组中再利用双指针进行判断。时间复杂度为O(n)，空间复杂度为O(n)。
判断是否是回文链表的关键就是找到前半部分的结点与与之对应的后半部分的结点存储的数值是否相等，那如何找到前半部分结点对应的后半部分结点，可以利用"删除倒数第n个结点"的思想，找到"第一个结点对应的倒数第一个结点"然后再进行比较判断，从头找到尾没有问题但是做了一半的重复工作，所以可以先找到链表的中间结点，只对前半部分的结点"找与之对应的后半部分结点"即可。
第二种思路找到"第一个结点"和"倒数第一个结点进行比较"；其实我们在找到中间结点之后可以把前半部分[或者后半部分]链表进行反转与后半部分[或者前半部分]进行比较。

相比较来说还是第三种思路最简洁和容易理解，对于第二种方法我们在遍历的过程中还要记录当前结点是第几个结点，并且要多次遍历链表找到结点对应的倒数结点。
第三种有一个小细节需要注意，要考虑链表的元素个数的奇偶性[由于我们在输入数据的时候输入了链表的元素个数所以就不需要再次遍历链表获取元素总数了]
这里采用第三种思路编写程序

#include<iostream>
using namespace std;


//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
int main(){
	//head
	listnode *head=nullptr,*mv=nullptr;
	int n,num;cin>>n;
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		if(!head) head=node;
		else{
			node->next = mv->next;
			mv->next=node;
		}
		mv=node;
	}
	// find middle node and reverse list
	listnode *fast=head,*slow=head,*pre=nullptr;
	while(fast&&fast->next){
		fast=fast->next->next;
		//reverse
		listnode *te = slow->next;
		
		slow->next=pre;
		pre=slow;
		slow=te;
		
	}
	listnode *h1 = pre,*h2=nullptr;
	//odd
	if(n&1){
		//1 2 3 slow point to 2
		h2 = slow->next;

	}else{
		//1 2 3 4 slow point to 3
		h2 = slow;
	}
	while(h1){
		if(h1->val!=h2->val) {cout<<"NO"<<endl;return 0;}
		h1=h1->next;
		h2=h2->next;
	}
	cout<<"YES"<<endl;
	return 0;
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	var head,mv *listnode

	var n,num int
	fmt.Scan(&n)
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		if head==nil {
			head=node
		}else{
			node.next=mv.next
			mv.next=node
		}
		mv=node
	}

	//find middle node and reverse list
	fast,slow:=head,head
	var pre *listnode
	for fast!=nil&&fast.next!=nil{
		fast=fast.next.next
		//reverse
		te:=slow.next
		slow.next=pre
		pre=slow
		slow=te
	}
	//odd
	var h1,h2 *listnode
	h1=pre
	if n&1==1{
		//1 2 3 slow point to 2
		h2=slow.next
	}else{
		//1 2 3 4 slow point to 3
		h2=slow
	}
	for h1!=nil{
		if h1.val!=h2.val{
			fmt.Println("NO")
			return 
		}
		h1,h2=h1.next,h2.next
	}
	fmt.Println("YES")
}

环形链表||

题目：

给定一个链表。如果链表存在环的话，返回开始入环的第一个结点；若不存在环的话返回null。
环的定义:如果链表中有某个结点，可以通过连续跟踪next指针再次到达，链表中存在环。

输入

输入整数n和pos分别表示链表元素个数和环的位置，如果pos为-1则链表不存在环

输出

判断链表是否有环，有的话输出环的入口位置对应的数值，没有的话输出-1

测试样例

样例1
4 1
3 2 0 -4
返回索引为1的链表结点2
样例2
2 0
1 2
返回索引为0的链表结点1
样例3
1 -1
1
-1

思路:

首先了解一下环的定义:如果链表中有某个结点，可以通过连续跟踪next指针再次到达，链表中存在环。比较容易想到的就是把遍历到的结点存储到一个集合当中，加入之前先判断这个结点之前是否出现过即是否存储在集合中，如果出现过说明有环并且找到了环的入口地址。没有的话说明没有环，时间复杂度就是O(n)空间复杂度就是O(n)
还有一种思路就是基于"数学思想"，利用的是双指针。具体分析可以参考https://leetcode.cn/problems/linked-list-cycle-ii/solutions/441131/huan-xing-lian-biao-ii-by-leetcode-solution/

hashmap

#include<iostream>
#include<unordered_set>
using namespace std;

//list node
struct listnode{
	int val;//data
	listnode *next;//next pointer
	//construct
	listnode():val(0),next(nullptr){}
	listnode(int v):val(v),next(nullptr){}
	listnode(int v,listnode*n):val(v),next(n){}
};
listnode *detectCycle(listnode *head);
int main(){
	//head 
	listnode *head=nullptr,*mv=nullptr,*te=nullptr;
	int n,pos,num;cin>>n>>pos;
	for(int i=0;i<n;++i){
		cin>>num;
		listnode *node = new listnode(num);
		if(!head) head=node;
		else{
			node->next = mv->next;
			mv->next=node;
		}
		mv=node;
	}
	if(pos>=0){
		te = head;
		while(pos--) te=te->next;
		mv->next = te;
	}

	listnode *node = detectCycle(head);

	if(node) {
		cout<<node->val<<endl;
	}else{
		cout<<-1<<endl;
	}
	return 0;
	
}

listnode *detectCycle(listnode *head){
	unordered_set< listnode* > se;
	while(head){
		if(se.count(head)) return head;
		se.insert(head);
		head=head->next;
	}
	return nullptr;
}

package main

import "fmt"

type listnode struct{
	val int
	next *listnode
}


func newlistnode()*listnode{
	return new(listnode)
}

func newlistnode1(num int)*listnode{
	node:= new(listnode)
	node.val=num
	return node
}

func newlistnode2(num int,n *listnode)*listnode{
	node:= new(listnode)
	node.val=num
	node.next=n
	return node
}

func main(){
	//head
	var head,mv,te *listnode

	var n,pos,num int
	fmt.Scan(&n,&pos)
	for i:=0;i<n;i++{
		fmt.Scan(&num)
		node:=newlistnode1(num)
		if head==nil{
			head=node
		}else{

			node.next=mv.next
			mv.next=node
		}
		mv=node
	}
	if pos>=0{
		te=head
		for pos>0{
			pos--
			te=te.next
		}
	}
	mv.next=te
	node:=detectCycle(head)
	if node!=nil{
		fmt.Println(node.val)
	}else{
		fmt.Println(-1)
	}
}

func detectCycle(head *listnode)*listnode{
	se:=map[*listnode]struct{}{}
	for head!=nil{
		if _,ok:=se[head];ok{
			return head
		}
		se[head]=struct{}{}
		head=head.next
	}
	return nil
}

fast-slow

//double pointer
listnode* detectCycle1(listnode*head){
        //fast_slow pointer
        listnode *fast=head,*slow=head;
        while(fast&&fast->next){
                fast=fast->next->next;
                slow=slow->next;
                //先判断是否有环
                if(fast==slow){
                        //确定有环之后，找出环的入口地址
                        slow=head;
                        while(slow!=fast){
                                slow=slow->next;
                                fast=fast->next;
                        }
                        return slow;
                }
        }
        return nullptr;
}

//double pointer
func detectCycle1(head *listnode)*listnode{
        fast,slow:=head,head
        for fast!=nil&&fast.next!=nil{
                fast=fast.next.next
                slow=slow.next
                if fast==slow{
                        slow=head
                        for slow!=fast{
                                slow,fast=slow.next,fast.next
                        }
                        return slow
                }
        }
        return nil
}

数组VS链表

时间复杂度	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

数组和链表的对比不能只局限于时间复杂度；在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，提高访问的效率。链表在内存中并不是连续存储无法有效利用CPU缓存机制。
数组的缺点是大小固定占用一块固定大小且连续的内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致OOM。如果声明的数组过小，有可能出现不够用的情况，后期还需要申请一块更大的连续内存并将旧内存的数据拷贝到新内存这是非常耗时的操作。
如果代码对内存的要求非常严格，建议使用数组。因为链表需要额外的空间存储结点的地址，并且频繁的删除插入会导致内存碎片。

Go–fmt.Scan VS fmt.Scanf

fmt.Scan和fmt.Scanf是Go中用于从标准输入读取数据的函数。区别在于参数的使用和具体的输入格式。
fmt.Scan函数使用空格作为分隔符，按照顺序读取输入的值并将其存储在提供的参数中，会自动识别不同类型的数据。得到的输入值会自动去除换行符。

package main
import "fmt"
func main(){
        var str,str1 string
        var n int
        fmt.Scan(&str,&str1)
        fmt.Scan(&n)
        fmt.Println(str,str1,n)
}

在这里插入图片描述

fmt.Scanf函数允许指定具体的格式字符串读取输入。需要提供一个或者多个格式说明符指定输入值的类型。如果格式字符不包含换行符输入中的回车会被当作普通字符处理。解决方式就是在格式字符串中显示添加\n读取并处理换行符

package main
import "fmt"
func main(){
        var str,str1 string
        var n int
        fmt.Scanf("%s%s",&str,&str1)
        fmt.Scan("%d",&n)
        fmt.Println(str,str1,n)
}

在这里插入图片描述
通过运行结果可以看出，Scanf将换行作为普通字符处理；解决方法显示加入\n格式字符

package main
import "fmt"
func main(){
        var str,str1 string
        var n int
        fmt.Scanf("%s%s\n",&str,&str1)
        fmt.Scanf("%d",&n)
        fmt.Println(str,str1,n)
}

在这里插入图片描述

如何读入带有空格的字符串

package main

import (
        "fmt"
        "bufio"
        "os"

        "strings"
        "reflect"
)


func main(){
      //第一种方法得到的是[]string
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        input:=scanner.Text()
        words:=strings.Fields(input)
        fmt.Println(words,getType(words))
        for _,str:=range words{
                fmt.Printf("%s\t",str)
        }
        fmt.Println()
        //第二种方法得到的是string 
        reader:=bufio.NewReader(os.Stdin)
        name,_:=reader.ReadString('\n')
        name=name[:len(name)-1]
        fmt.Println(name)
        fmt.Println(getType(name))
}
//利用反射获取元素的类型
func getType(v interface{})reflect.Type{
        return reflect.TypeOf(v)
}

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_46290302/article/details/135436771
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

数组、链表专题

文章目录

线性表

数组

为什么数组从0开始编号而不是从1开始

数组VS容器

算法题

二分查找

移除元素

有序数组的平方

长度最小的子数组

螺旋矩阵

链表

链表结构

单链表

循环链表

双向链表

双向循环链表

链表代码编写的小技巧

理解指针或引用的含义

警惕指针丢失和内存泄露

利用哨兵简化实现难度

重点留意边界条件处理

算法题

两个有序链表的合并

移除链表元素

反转链表

两两交换链表中的结点

删除链表的倒数第N个结点

回文链表

环形链表||

数组VS链表

Go–fmt.Scan VS fmt.Scanf