最近复习数据结构，加强下自己的基础。在复习中遇到的问题在这里做下笔记。
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
单链表的定义：
typedef struct LNode{
int data; // data 中存在结点的数据域
struct LNode *next; // 指向后继结点的指针
}LNode; // 定义单链表结点类型单链表的构造方法（尾插法和头插法）
（1）尾插法
void CreateListR(LNode *&C, int a[], int n){
LNode *s, *r; //s 用来指向新申请结点， r 始终指向C的终端结点
int i;
C = (LNode *)malloc(sizeof(LNode *)); //申请C的头结点空间
C -> next = NULL;
r = C; //r 指向 C 的头结点，因为此时 C 的头结点就是 C 的终端结点
for (i=0;i<n;i++){
s = (LNode *)malloc(sizeof(LNode *)); //s指向新申请结点
s -> data = a[i];
r -> next = s; //r 接纳新结点
r = r -> next; //r 指向终端结点，以便接纳下一个到来的结点
}
r -> next = NULL; //所有元素都装入了链表 C 中，将 C 的终端结点的指针域置为NULL
}
（2）头插法
void CreateListH(LNode *&C, int a[], int n){
LNode *s;
int i;
C = (LNode *)malloc(sizeof(LNode *)); //申请C的头结点空间
C -> next = NULL;
for (i=0;i<n;i++){
s = (LNode *)malloc(sizeof(LNode *)); //s指向新申请结点
s -> data = a[i];
s -> next = C -> next; //s 所指向新结点的指针域 next 指向 C 中的开始结点
C -> next = s ; //头结点的指针域 next 指向 s 结点， 使得 s 结点成为了新的开始结点
}
}
链表删除( 删除 p->next )
q = p -> next;
p -> next = p -> next -> next;
free(q);
链表的插法（头插法和尾插法）和删除是所有链表知识的基础知识，很多操作都是由着三个基本操作组成。
下面介绍一个链表的综合题目（leetCode上面的）
给定两个非负整数（个位整数）的单链表，将两个单链表中对应元素相加的到的值保存到一个单链表中
输入: [2, 4, 3]
[5, 6, 4]
输出: [7, 0 ,8]
题目分析：（根据题目描述和输入输出实例）每个单链表中元素的值相加，如果小于10，则得到的值即为所求的值，如果相加的值大于10，那么所要求的值为个位上的数，同时十位上的1要加到下次运算中。
思想分析：可以创建一个单链表，让其长度为输入链表中最大的长度。因为单链表没有提供length的属性，那么只有通过变量才能得到最大的长度，这样会加大运行的负担，因此在遍历单链表的时候，判断单链表是否为空，如果一个单链表为空，另一个还没有为空，那么为空的那个单链表往后的值可以认为是0，这样就不会影响最终的计算，一次遍历就可以达到最大的长度。需要注意的是，如果遍历完后，最后一次的得到的值大于10，那么需要在最后再添加一个结点，来保存得到的十位数。
代码实现（C++）
#include <iostream>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//使用模板定义一个函数getArrayLen,该函数将返回数组array的长度
template <class T>
int getArrayLen(T& array) {
return (sizeof(array) / sizeof(array[0]));
}
class Solution {
public:
/**
* 用尾插法创建一个没有头结点的链表
*/
ListNode* createListE(int array[], int n){
ListNode *r, *s;
ListNode* list = (ListNode *)malloc(sizeof(ListNode *));
list->next = NULL;
r = list;
for (int i = 0; i < n; ++i) {
s = (ListNode *)malloc(sizeof(ListNode *));
s -> val = array[i];
r -> next = s;
r = r->next;
}
r->next = NULL;
return list->next;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//链表不含头结点
int flag = 0; //定义标示符，初始化为0，链表值相加大于10为1，否则为0
ListNode* p = l1;
ListNode* q = l2;
ListNode* l3 = (ListNode*)malloc(sizeof(ListNode*)); //申请l3的头结点空间（可以创建带头结点的链表，然后返回l3->next, 去除头结点即可）
l3 -> next = NULL;
ListNode* r = l3; //r 指向 l3 的始终最后一个结点
int valp, valq; //p，q链表对应位置的值
while (p != NULL || q != NULL){ // 一个不为空，就继续（得到最大的长度）
valp = (p==NULL?0:p->val); // p为空的话，对应值为0；否则为p链表的值
valq = (q==NULL?0:q->val);
ListNode* s = (ListNode*)malloc(sizeof(ListNode*)); //s指向新申请结点
if (valp + valq + flag < 10){ //小于10的情况
s -> val = (valp + valq + flag);
flag = 0; // 小于10设为0，不影响下次的计算
}else{ //大于10的情况
s -> val = (valp + valq + flag) % 10; //取个位的值
flag = 1; // 大于10设为1，下次计算加1
}
//链表尾插法
r -> next = s;
r = r -> next;
if (p != NULL) p = p -> next; //p不为空的话，向后移动一个位置
if (q != NULL) q = q -> next;
}
if (flag == 1 ){ //最后一次结果大于10的情况
ListNode* s = (ListNode*)malloc(sizeof(ListNode*)); //再次申请新结点
//将新结点用尾插法插入到l3链表中
s -> val = flag;
r->next = s;
r = r->next;
}
r -> next = NULL; //所有元素都装入了链表 l3 中，将 l3 的终端结点的指针域置为NULL
return l3->next; //返回去除头结点的 l3 链表
}
};
int main(int argc, const char * argv[]) {
//测试用例
int a[] = {2,4,3};
int b[] = {5,6,4};
// int a[] = {3};
// int b[] = {7,6};
//
// int a[] = {5};
// int b[] = {5};
//
// int a[] = {3, 8};
// int b[] = {2};
//计算数组的长度
int alength = getArrayLen(a);
int blength = getArrayLen(b);
Solution s;
//尾插法得到无头结点的单链表
ListNode* l1 = s.createListE(a, alength);
ListNode* l2 = s.createListE(b, blength);
//计算两个单链表的和
ListNode* l3 = s.addTwoNumbers(l1, l2);
ListNode* r = l3;
while (r!=NULL) {
cout<<r->val<<",";
r = r->next;
}
cout<<endl;
return 0;
}
例题2：判断一个链表是否有环
思路：定义两个指针，一快一慢，当两个指针相遇，则证明有环，否则没有环。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//找到第一次相遇的节点（如果有环，返回相遇的节点，没有环，返回NULL）
bool cycleList(ListNode *head){
ListNode *pSlow = head;//慢指针
ListNode *pFast = head;//快指针
while (pFast != NULL && pFast -> next != NULL){
pFast = pFast -> next -> next;
pSlow = pSlow -> next;
if (pFast == pSlow) return true;//有环，返回true
}
return false;//无环 返回false
}例题3：如果一个链表有环，找出环的入口
分析：同样定义2个指针，然后将其中一个指针向后移动环的长度n，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，后面的那个指针已经围绕环走了一圈，回到了入口结点，两个指针相遇。
求环的长度，可以先找出环中任意的一个结点，然后从这个结点出发，一边向后移动，一边计数，再次返回这个结点的时候，就可以得到环的长度了。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//找到第一次相遇的节点（如果有环，返回相遇的节点，没有环，返回NULL）
ListNode *meetingNode(ListNode *head){
ListNode *pFast = head;//快指针
ListNode *pSlow = head;//慢指针
while(pFast != NULL && pFast -> next != NULL){
pFast = pFast -> next -> next;
pSlow = pSlow -> next;
if (pFast == pSlow) return pFast;//有环，返回相遇的节点
}
return NULL;//无环 返回NULL
}
ListNode *detectCycle(ListNode *head) {
ListNode *meetingLN = meetingNode(head);
if (meetingLN == NULL) return NULL;
//计算环的长度，找到第一次的公共顶点，然后再遍历一圈，即可确定长度
ListNode *pHeadNode = meetingLN;
int count = 1;
while (pHeadNode -> next != meetingLN){
pHeadNode = pHeadNode -> next;
++count;
}
//创建2个指针，一个指向头节点，一个向后移动环的长度，两个指针相遇的地方就是环的入口
pHeadNode = head;
ListNode *pLastNode = head;
while(count){
pLastNode = pLastNode -> next;
--count;
}
while(pHeadNode != pLastNode){
pHeadNode = pHeadNode -> next;
pLastNode = pLastNode -> next;
}
return pLastNode;
}