Leetcode链表考察(Python、C语言和java实现)_leetcode如何创建链表python

写在前面

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

/*  
 *	专业术语:
 *		首节点：存放第一个有效数据的节点
 *		尾节点：存放最后一个有效数据的节点
 *		头结点
 *			1、头结点的数据类型和【首节点的类型】是--摸一样的
 *			2、头结点是【首节点】前面的那个节点。
 *			3、头结点并【不存放有效数据】。
 *			4、设置头结点的目的是为了方便对链表的操作。
 *		头指针
 *			存放头结点地址的指针变量
 *		确定一个链表需要一个参数
 *			头指针
 */

#include<stdio.h>
#include<stdlib.h>  //提供malloc()和free()
#include <malloc.h> //开辟空间
#include <string.h> //提供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<index
		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。