链表就是N个结构体
链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束
单链表
链表的C写法
///> 思路就是把end指向 新创建的 然后把新创建的作为新的end
LinkList *creatList(int n){
LinkList *head, *node, *end;//定义头节点，普通节点，尾部节点；
head = (LinkList*)malloc(sizeof(LinkList));//分配地址
end = head; //若是空链表则头尾节点一样 等于就是同一个
for (int i = 0; i < n; i++) {
node = (LinkList*)malloc(sizeof(LinkList));
node->score = i;
end->next = node; //这个时候的end是。head 就是操作的head 就是给end赋值 指向新创建的
end = node; //这个时候的end是。node 然后把新创建的作为end
}
end->next = NULL;//结束创建
return head;
}
链表有什么用？插入/删除速度很快 而且不用对整个链表 地址不一定连续
相对于数组来说:
优点: 通过索引(数组下标)可以很快地访问数组元素;
缺点: 插入/删除元素需要对数组进行调整, 效率低;
而链表:
优点：插入/删除速度很快，而且不用对整个链表进行调整；
缺点：只能进行顺序访问，不能随机访问（像数组一样用下标）；
所以，链表在一些需要快速插入／删除，而不太关心或者不需要随机访问的情况下使用
链表是动态的进行存储分配的一种结构。
我们知道，用数组存放数据时，必须事先定义固定的长度（即元素个数）。如果事先难以确定元素个数，则必须把数组定义的足够大，以便存放，显然这样会浪费内存。
而链表可根据需要开辟内存单元，不会浪费内存。
链表有一个“头指针”变量，它存放一个地址，该地址指向一个元素，这个元素又指向下一个元素......直到最后一个元素，该元素不再指向其他元素，称为“表尾”，链表到此结束。
两数相加
/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
*/
链表反转：
去面试被问到一个问题，怎么把一个链表反转(用原链表)，自己在网上找了到了一篇文章，http://blog.csdn.net/sicofield/article/details/8850269，原作者给出了三种方法，
方法一：将链表数据全部读到数组中，然后在倒序输出。
方法二：就是我下面要讲的。
方法三：从第二个结点开始，把之后的每个结点都插入到第一个结点之后，最后在把第一个结点挪到表尾。
第二题解答
///> 创建链表 如果输入 2 实际创建了3个 head是自己创建的
LinkList *creatList(int n);
///> 链表反转
LinkList* reverseList(LinkList* head);
///> 修改链表
void changeList(LinkList *list,int n,int value);
///> 插入链表 只可以插入一个节点note
void insertList(LinkList *list,int n,int value);
///> 删除链表
void deletList(LinkList *list,int n);
///> 两数之和
LinkList* addTwoNumbers(LinkList* l1, LinkList* l2);
void printLinkList(LinkList * L);
int linkListCount(LinkList * h);
int *linkListArr(LinkList * h);
int linkListValue(LinkList * h);
int getIntSize(int number);
int main(int argc, const char * argv[]) {
LinkList *list = creatList(3);
printLinkList(list);
printf("下面是反转 ----- \n");
LinkList *reverse = reverseList(creatList(3));
printLinkList(reverse);
printf("下面是修改 ----- \n");
changeList(reverse, 1, 10);
printLinkList(reverse);
printf("下面是插入 ----- \n");
insertList(reverse, 1, 9);
printLinkList(reverse);
printf("下面是删除 ----- \n");
deletList(reverse,1);
printLinkList(reverse);
printf("下面是两个链表之和 ----- \n");
LinkList *list1 = creatList(3);
LinkList *list2 = creatList(3);
printLinkList(list1);
printLinkList(list2);
LinkList *list3 = addTwoNumbers(list1, list2);
printLinkList(list3);
return 0;
}
#pragma mark - C 语言链表
///> 创建链表
///> 思路就是把end指向 新创建的 然后把新创建的作为新的end
LinkList *creatList(int n){
LinkList *head, *node, *end;//定义头节点，普通节点，尾部节点；
head = (LinkList*)malloc(sizeof(LinkList));//分配地址
end = head; //若是空链表则头尾节点一样 等于就是同一个
for (int i = 0; i < n; i++) {
node = (LinkList*)malloc(sizeof(LinkList));
node->score = (i + 6);
end->next = node; //这个时候的end是。head 就是操作的head 就是给end赋值 指向新创建的
end = node; //这个时候的end是。node 然后把新创建的作为end
}
end->next = NULL;//结束创建
return head;
}
///> 链表反转 head 还是head 因为head是没有值的 其他节点都有值
///> 错误的点 two->next 赋值了改变了的值 如何让最后一个节点的值不改变
///> one->next 是下一个节点 head 指向one->next。保留上一个节点 使得
LinkList* reverseList(LinkList* head) {
if(head==NULL) return NULL;
LinkList *one = head->next;
LinkList *temp = NULL;
while (one->next) {
///> 这次的最后一个节点
LinkList *two = one->next;
///> 下次的最后一个节点
LinkList *three = two->next;
///> 指向最后一个节点
head->next = two;
///> 这次的最后一个节点 指向上次的最后一个节点
if (temp == NULL) {//> 这是第一次循环
two->next = one;
} else {
two->next = temp;
}
///> 指向下次的最后一个节点
one->next = three;
temp = two;
}
one->next = NULL;
return head;
}
///> 修改链表 节点个数。1 2 3。是3个
void changeList(LinkList *list,int n,int value) {
LinkList *t = list;
int i = 0;
while (i < n && t != NULL) {
t = t->next;
i++;
}
if (t != NULL) {
t->score = value;
}
else {
puts("节点不存在");
}
}
///> 插入链表 ///> 3 9 10 1
void insertList(LinkList *list,int n,int value) {
if (n == 0 || n > linkListCount(list)) {
puts("节点不存在");
return;
}
LinkList *t = list;
LinkList *last = NULL,*next = NULL;
LinkList *node = (LinkList *)malloc(sizeof(LinkList));
node->score = value;
if (n == 1) {
last = t;
next = t->next;
} else {
int i = 0;
while (i < n && t != NULL) {
t = t->next;
if (i == (n - 2)) {
last = t;
} else if (i == (n - 1)) {
next = t;
}
i++;
}
}
last->next = node;
node->next = next;
}
///> 删除链表
void deletList(LinkList *list,int n) {
if (n == 0 || n > linkListCount(list)) {
puts("节点不存在");
return;
}
LinkList *t = list;
LinkList *last = NULL,*next = NULL;
if (n == 1) {
last = t;
next = t->next->next;
} else {
int i = 0;
while (i < n && t != NULL) {
t = t->next;
if (i == (n - 2)) {
last = t;
} else if (i == (n - 1)) {
next = t->next;
}
i++;
}
}
last->next = next;
}
void printLinkList(LinkList * h) {
printf("输出");
int i = 0;
while (h->next != NULL) {
h = h->next;
i++;
printf(" %d",h->score);
}
printf(" \n");
}
int linkListCount(LinkList * h) {
int i = 0;
while (h->next != NULL) {
h = h->next;
i++;
}
return i;
}
int *linkListArr(LinkList * h) {
int count = linkListCount(h);
int *arr = (int *)malloc(count);
int i = 0;
while (h->next != NULL) {
h = h->next;
arr[i] = h->score;
i++;
}
return arr;
}
int linkListValue(LinkList * h) {
int count = linkListCount(h);
int *arr = linkListArr(h);
int value = 0;
for (int i = 0 ; i < count; i++) {
int a = arr[i];
value = value + a * pow(10, count - i - 1);
}
return value;
}
int getIntSize(int number) {
int count = 0;
while (number > 0) {
count += 1;
number = (number / 10);
}
return count;
}
/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
*/
LinkList* addTwoNumbers(LinkList* list1, LinkList* list2) {
LinkList *revers1 = reverseList(list1);
LinkList *revers2 = reverseList(list2);
int a = linkListValue(revers1);
int b = linkListValue(revers2);
int c = a+b;
int cConut = getIntSize(c);
int *arr = (int *)malloc(cConut);
int temp = 0;
for (int i = 0; i < cConut; i++) {
int a = pow(10, cConut - 1 - i);
int b = c / a;
if (temp != 0 ) b = temp / a;
arr[i] = b;
temp = c % a;
}
LinkList *head, *node, *end;
head = (LinkList*)malloc(sizeof(LinkList));
end = head;
for (int i = 0; i < cConut; i++) {
node = (LinkList*)malloc(sizeof(LinkList));
node->score = arr[i];
end->next = node;
end = node;
}
end->next = NULL;
LinkList *revers3 = reverseList(head);
return revers3;
}
///>简单求法
struct ListNode* addTwoNumbersw1(struct ListNode* l1, struct ListNode* l2) {
int listC=0;
struct ListNode *p;
p = l1->next;
while(p)
{
listC++;
p=p->next;
}
int *arr = (int *)malloc(listC + 1);
int number = 0,temp = 0;
int i = 0;
while (l1->next != NULL) {
l1 = l1->next;
l2 = l2->next;
number = l1->val + l2->val + temp;
arr[i] = number % 10;
temp = number / 10;
i++;
}
int *listA;
int endC = 0;
if (temp > 0) {
arr[listC] = temp;
listA = arr;
endC = listC + 1;
} else {
listA = (int *)malloc(listC);
endC = listC;
for (int i = 0; i < listC; i++) {
listA[i] = arr[i];
}
}
struct ListNode *head, *node, *end;
head = (struct ListNode*)malloc(sizeof(struct ListNode));
end = head;
for (int i = 0; i < endC; i++) {
node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = listA[i];
end->next = node;
end = node;
}
end->next = NULL;
free(arr);
if (listA) {
free(listA);
}
return head;
}
