第一章
链表
- 了解单链表和双链表的结构;
- 在单链表或双链表中实现遍历、插入和删除;
- 分析在单链表或双链表中的各种操作的复杂度；
- 在链表中使用双指针技巧（快指针慢指针技巧）；
- 解决一些经典问题，例如反转链表；
- 分析你设计的算法的复杂度；
- 积累设计和调试的经验
my list：
typedef struct Link{
int date;
struct Link* next;
} MyLinkedList;
/** Initialize your data structure here. */
MyLinkedList* myLinkedListCreate() {
MyLinkedList *head=( MyLinkedList*)malloc(sizeof(MyLinkedList));
head->next=NULL;
return head;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int myLinkedListGet(MyLinkedList* obj, int index) {
MyLinkedList *p=obj->next;
int j=0;
while(p!=NULL && jnext;
}
if(p==NULL||index<0)
return -1;
else return p->date;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
MyLinkedList* p=obj;
MyLinkedList* newP=( MyLinkedList*)malloc(sizeof(MyLinkedList));
newP->date=val;
newP->next=p->next;
p->next=newP;
return ;
}
/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
MyLinkedList *tmp=obj;
MyLinkedList* newp=( MyLinkedList*)malloc(sizeof(MyLinkedList));
newp->date=val;
newp->next=NULL;
if(tmp==NULL){
obj=newp;
return;
}
while(tmp->next!=NULL){
tmp=tmp->next;
}
tmp->next=newp;
return ;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
MyLinkedList *P=obj->next,*tmp;
if(index<=0)
{
MyLinkedList *newP=( MyLinkedList*)malloc(sizeof( MyLinkedList));
newP->date=val;
newP->next=P;
obj->next=newP;
return;
}
int count=0;
for( ; P!=NULL && countnext) ;
if(P==NULL)
return;
if(countdate=val;
newP->next=P->next;
P->next=newP;
return;
}
/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
MyLinkedList *P=obj->next,*deleteP;
int count=0;
if(index<0)
return;
while(P!=NULL && countnext;
}
if(P==NULL)
return;
else{
deleteP=P->next;
if(deleteP==NULL)
return;
else{
if(index==0){
obj->next=obj->next->next;
return;
}
else
P->next=deleteP->next;
free(deleteP);
return;
}
}
}
void myLinkedListFree(MyLinkedList* obj) {
MyLinkedList *p=obj,*q=obj->next;
while(q!=NULL){
free(p);
p=q;
q=q->next;
}
} 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。
假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
链表中的双指针
从一个经典问题开始
给定一个链表，判断表中是否有环？
哈希表中有相应的解决方案，但是这里使用双指针有一个更有效的方法想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。这正是我们在链表中使用两个速度不同的指针时会遇到的情况：
1. 如果没有环，快指针将停在链表的末尾。
2. 如果有环，快指针最终将与慢指针相遇。
所以剩下的问题是：这两个指针的适当速度应该是多少？一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。那其他选择呢？它们有用吗？它们会更高效吗？
判断链表是否交叉
因为链表长度是不同的，因此在判断是否交叉的时候，可以设计双指针，即先通篇遍历完两次，看末尾的地址是否相同，若相同则肯定交叉，然后开始判断。因为正如上文所说，链表的长度不一定的，因为必有长短（或者相同），先遍历求出长度，求出长度后，就有长度差，长的链表先移动长度差的距离后，两个链表就在同一个起点上，开始一起遍历，因此时间复杂度是o（n）（遍历了3次）
下面是代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(headA==NULL || headB==NULL)
return NULL;
struct ListNode *p1=headA,*p2=headB;
int len1=0,len2=0,diff=0;
while((p1->next)!=NULL){
len1++;
p1=p1->next;
}
while((p2->next)!=NULL){
len2++;
p2=p2->next;
}
if(p1!=p2)
return NULL;
else{
if(len1>len2){
p1=headA;
p2=headB;
diff=len1-len2;
}
else{
p1=headB;
p2=headA;
diff=len2-len1;
}
for(int i=0;inext;
}
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}
return p1;
}
} 第二章
图的存储方法
在存储无向图和有向图时，其存储方法有所不同
大致上可以用：
- 邻接矩阵：数组表达
- 邻接表：链表（多用于有向图）
- 十字链表：链表（多用于有向图）
- 邻接多重表：链表（无向图）
邻接矩阵–数组存储
顶点的表达：由顶点索引和顶点数据构成 因此弧也就与邻接矩阵相关
struct Node{
顶点索引;
顶点数据;
};
struct Map{
顶点数组;//包含顶点
邻接矩阵;//顶点与边的表示都包含了
};邻接表–链式存储
邻接表与逆邻接表
顶点的表达:顶点索引 | 出弧链表头指针 | 顶点数据
弧的表达：弧头顶点索引 | 下一条弧指针 | 弧数据
struct Node{
顶点索引;
该顶点弧链表的头结点
顶点数据;
};
struct Arc{
指向的顶点索引;
指向下一条弧的指针;
弧信息;
};
struct Map{
顶点数组;
};十字链表–链式存储
顶点的表达：
顶点索引 | 顶点数据 | 以该顶点为弧尾的弧结点指针 | 以该顶点为弧头的弧结点指针
弧的表达：
弧尾顶点索引 | 弧头顶点索引 | 弧尾相同的下一条弧的指针 | 弧头相同的下一条弧的指针 | 弧的数据
struct Node{
顶点索引;
顶点数据;
第一条入弧结点指针;
第一条出弧结点指针;
};
struct Arc{
弧尾顶点索引;
弧头顶点索引;
指向下一条弧头相同的弧的指针;
指向下一条弧尾相同的弧的指针;
弧信息;
};
struct Map{
顶点数组;
};邻接多重表–链式存储
顶点的表达：
顶点索引 | 顶点数据 | 连接该顶点的边 |
弧的表达：
A顶点索引 | B顶点索引 | 与A顶点相连接的下一条边的指针 | 与B顶点相连接的下一条边的指针 | 弧的数据
struct Node{
顶点索引;
顶点数据;
第一条边结点指针;
};
struct Egde{
顶点A索引;
顶点B索引;
连接A的下一条边的指针;
连接B的下一条边的指针;
弧信息;
};
struct Map{
顶点数组;
};
