• Leetcode链表考察(Python、C语言和java实现)


    写在前面

    创建一个链表头文件,其中包含的基本操作和定义,方便以后调用

    /*  
     *	专业术语:
     *		首节点:存放第一个有效数据的节点
     *		尾节点:存放最后一个有效数据的节点
     *		头结点
     *			1、头结点的数据类型和【首节点的类型】是--摸一样的
     *			2、头结点是【首节点】前面的那个节点。
     *			3、头结点并【不存放有效数据】。
     *			4、设置头结点的目的是为了方便对链表的操作。
     *		头指针
     *			存放头结点地址的指针变量
     *		确定一个链表需要一个参数
     *			头指针
     */
    
    #include
    #include  //提供malloc()和free()
    #include  //开辟空间
    #include  //提供strcpy()等
    
    typedef struct LNode{ //定义单链表结点类型
    	int data; //数据域,可以是别的各种数据类型,本文统一用int类型
    	struct LNode *next; //指针域
    }LNode, *LinkList;    //LNode等价于struct LNode; LinkList等价于truct LNode*
    
    
    // 初始化单链表
    LinkList Init_Table(LinkList L)
    {
    	L = (LinkList)malloc(sizeof(LNode));
    	L->next = NULL;
    	return L;
    }
    
    //头插法建立单链表
    LinkList Head_Insert(LinkList L)
    {
    	LNode* s; int x;int len;
    
    	L = (LinkList)malloc(sizeof(LNode));
    	L->next = NULL;
    
    	printf("头插法建立单链表,请输入链表长度:");
    	scanf("%d",&len);
    
    	for(int i = 0; i<len; i++)
    	{
    		printf("请输入要插入的整数:");
    		scanf("%d",&x);
    		s = (LinkList)malloc(sizeof(LNode));  //为s分配内存空间
    		s->data = x;
    		s->next = L->next;
    		L->next = s;
    	}
    	return L;
    }
    
    // 尾插法建立带表头单链表
    LinkList Tail_Insert(LinkList L)
    {
    
    	LNode* s, *r;   // r为表尾指针。
    	int x,len;
    
    	L = (LinkList)malloc(sizeof(LNode));
    	L->next = NULL;
    
    	r = L;
    
    	printf("使用尾插法建立单链表,请输入链表长度:");
    	scanf("%d",&len);
    
    	for(int i = 0; i<len; i++)
    	{
    		printf("请输入要插入的整数:");
    		scanf("%d",&x);
    		s = (LinkList)malloc(sizeof(LNode));  //为s分配内存空间
    		s->data = x;
    		r->next = s; //开始链表为空,r指向表头, 现在需要将s节点链接到表头后面;
    		r = s;   //让r指针指向表尾, 之后每次插入都可以在表尾插入了
    	}
    	r->next = NULL;
    	return L;
    }
    
    // 遍历链表
    void Traverse_List(LinkList L)
    {
    	LNode* p = L->next;
    	while(NULL != p)
    	{
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    //带头结点的单链表, 根据索引,查找值
    LNode* Get_Elem(LinkList L,int index)
    {
    	int j = 1;
    	LNode* p = L->next;   //第一个值。
    	if(index==0)
    		return L;
    	if(index<0)
    		return NULL;
    	while(p && j < index)
    	{
    		p = p->next;  //进入循环,是从第二个值开始的,所以要j
    		j++;
    	}
    	return p;
    }
    
    //带有表头的单链表,按值查找表结点
    LNode* Locate_Elem(LinkList L, int key)
    {
    	LNode* p = L->next;
    	while(p->data!=key && p!=NULL)
    		p = p->next;
    
    	if(p!=NULL)
    		printf("找到了!");
    	else
    		printf("查找失败!");
    	return p; //找到后返回该节点指针,否则返回NULL.
    }
    
    //带表头,删除链表最后一个元素
    LinkList Del_Tail_Elem(LinkList L)
    {
    	LNode* p = L->next;               //第一个值, p 最后指向链表最后一个值
    	LNode* q = L;		              //q指向表头, q 最后指向链表倒数第二个值
    	while(NULL!=p->next)
    	{
    		q = p;          //如果后面还有元素,就把p的地址赋给q,然后让q指向后面的元素
    		p = p->next;
    	}
    	free(p);  // 释放最后一个值的内存
    	q->next = NULL;  //把倒数第二个值的指针域设置为空,就这样,最后一个值就删除完成了。
    	return L;
    }
    
    //带表头,删除链表第一个元素
    LinkList Del_Head_Elem(LinkList L)
    {
    	LNode* p = L->next;       //第一个值,
    	LNode* q = L;			//表头
    	q->next = p->next;
    	free(p);
    	return L;
    }
    
    //带表头,求表的长度
    int Length(LinkList L)
    {
    	int len;
    	LNode* p = L->next;   //第一个值。
    	if(NULL==L->next)
    		len = 0;
    	while(p!=NULL)
    	{
    		len = len + 1;
    		p = p->next;
    	}
    	return len;
    }
    
    // 带表头,末尾插入一个元素。
    LinkList Insert_Tail_Elem(LinkList L, int key)
    {
    	LNode* p = L->next;
    	LNode* s;
    	while(NULL!=p->next)
    		p = p->next;   // 循环直到p指向最后一个结点
    	s = (LinkList)malloc(sizeof(LNode)); // 为分配内存空间
    	s->data = key;
    	p->next = s;
    	s->next = NULL;
    	return L;
    }
    
    // 带表头,头插法入一个元素。
    LinkList Insert_Head_Elem(LinkList L, int key)
    {
    	LNode* s = NULL;
    	s = (LinkList)malloc(sizeof(LNode));
    
    	s->data = key;
    	s->next = L->next;
    	L->next = s;
    	return L;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194

    1. 合并排序 【Merge Sorted Array】

    给出两个排序的整数数组A和B,将B合并到A中作为一个排序的数组。注意:

    • 你可以假设A有足够的空间来容纳B的额外元素。
    • A和B中初始化的元素数分别为m和n。
    if __name__ == '__main__':
        list1 = [1, 3, 5, 7]
        list2 = [2, 4, 6, 8]
    
        list1 = list1+list2
        list1.sort()
        print(list1)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    2. 两数相加【add two numbers 】

    题目:给你两个代表两个非负数的链接列表。它们每位数字都是按照逆序的方式存储的,每个节点都包含一个数字。将这两个数字相加,并作为一个链表返回。

    • 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    • 输出:7 -> 0 -> 8
    • 解析:342 + 465 = 807

    C语言

    解析:因为逆序的方式进行存储:所以开始存储时采用头插法

    LinkList Add(LinkList L1,LinkList L2){//两个表带首节点进行相加
    
    	LNode* p = NULL;  // 指向最长的链表
    	LNode* q = NULL;  // 指向最短的链表
    
    	int pro = 0;   //表示进位
    
    	if(Length(L1)>=Length(L2))
    	{
    		p = L1->next;
    		q = L2->next;
    	}
    	else
    	{
    		p = L2->next;
    		q = L1->next;
    	}
    
    	while(q != NULL)   //q指针指向得为最短的链表
    	{
    		int temp = p->data + q->data + pro;
    		if (temp >= 10)
    		{
    			pro = 1;
    			p->data = temp % 10;
    		}
    		else
    		{
    			pro = 0;
    			p->data = temp;
    		}
    		p = p->next;
    		q = q->next;
    
    	}
    
    	while(p != NULL)
    	{
    		int temp = p->data + pro;
    		if (temp >= 10)
    		{
    			pro = 1;
    			p->data = temp % 10;
    		}
    		else
    		{
    			pro = 0;
    			p->data = temp;
    		}
    		p = p->next;
    	}
    
    	if(Length(L1)>=Length(L2))
    	{
    		printf("最后的进位数为:%d\n",pro);
    		if(pro != 0)
    			L1 = Insert_Tail_Elem(L1, pro);
    		return L1;
    	}
    	else
    	{
    		printf("最后的进位数为:%d\n",pro);
    		if(pro != 0)
    			L2 = Insert_Tail_Elem(L2, pro);
    		return L2;
    	}
    
    }
    
    int main(void)
    {
    	setvbuf(stdout,NULL,_IONBF,0);
    
    	LNode* Node = NULL;
    	LNode* Node2 = NULL;
    
    	LinkList L1 = Head_Insert(Node);
    	LinkList L2 = Head_Insert(Node2);
    
    
    	LinkList L3 = Add(L1, L2);
    	printf("两者相加的和为:");
    	Traverse_List(L3);
    
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    输出

    头插法建立单链表,请输入链表长度:2
    请输入要插入的整数:9
    请输入要插入的整数:9
    9 9 
    头插法建立单链表,请输入链表长度:3
    请输入要插入的整数:9
    请输入要插入的整数:9
    请输入要插入的整数:9
    9 9 9 
    最后的进位数为:1
    两者相加的和为:8 9 0 1 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3. Partition List

    给出一个链接列表和一个值x,对其进行分区,使所有小于x的节点排在大于等于x的节点之前。
    你应该保留两个分区中每个节点的原始相对顺序。例如,

    • 给定 1->4->3->2->5->2 和 x = 3,
    • 返回 1->2->2->4->3->5。
  • 相关阅读:
    计算机网络(下)
    系列二、什么是OOM?什么是StackOverflowError?有哪些方法分析?
    Docker镜像 配置ssh
    Android Startup启动优化
    Tomcat 接收请求并传递给工作线程池流程
    毕设准备---HelloServlet
    02.机器学习原理(复习)
    Python 中的万能之王 Lambda 函数
    驼峰命名法在编程中的应用
    【数据结构】插入排序
  • 原文地址:https://blog.csdn.net/qq_40926887/article/details/126037906