[数据结构与算法]Leetcode链表考察(Python、C语言和java实现)

写在前面

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

/*  
 *	专业术语:
 *		首节点：存放第一个有效数据的节点
 *		尾节点：存放最后一个有效数据的节点
 *		头结点
 *			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. 合并排序 【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)

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;
}

输出

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

3. Partition List

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

• 给定 1->4->3->2->5->2 和 x = 3，
• 返回 1->2->2->4->3->5。