链表

不支持随机访问，相比数组占用额外的空间，适合有大量插入和删除，无访问要求的操作。

 1.链表生成：头插和尾插

typedef struct node{
  int val;
  struct node* next;
}Node,*pNode;

int a[]={1,2,3,4,5};
pNode phead = (pNode)calloc(sizeof(Node),0);
phead->val = 0;
Phead->next = NULL;
pNode pcur = phead;
for(int i = 0;i < 5;++i)
{
  pNode p = (pNode)calloc(sizeof(Node),0);
  p->val = a[i];
  pcur->next = p;
  pcur = pcur->next;
}

2.链表倒转

void reverse (pNode head)
{
  pNode pReversedH = head;
  pNode pcur = head;
  pNode ppre = NULL;
  while(pcur)
  {
    pNode pnext = pcur->next;
    if(!pnext)
    {
          pReversedH = pcur;
     }
     pcur->next = ppre;
     ppre = pcur;
     pcur = pnext; 
  } 
}                   
        

3.查找链表的中间节点（快慢指针）

void midval(pNode p)
{    
    if(!p)
        return ;
    pNode fast=p,slow = p;
    while(fast)
    {
        if(fast->next)
            fast = fast->next->next;
        else 
            break;
        slow = slow->next;
     }
     pNode mid = slow;      
}

 4.查找倒数第k个指针

用两个指针，第一个先指向头指针向后偏移k的位置，第二个指针指向头指针，然后两个指针同时向后移动以为，直到第一个指针到末尾，则此时第二个指针就是结果。

5.判断链表是否有环，有环的话求入口（也是通过快慢指针，如果有环这两指针最终会相等）

求环入口：画图计算可得，相遇点到入口的距离刚好等于起点到入口的距离。

 6.判断两个链表是否交叉，就判断他们的尾结点是否相同，如果相同则有交点。

求交点，先遍历两链表，得出长度a，b。然后较长的链表从表头偏移|a-b|，然后两链表向后依次移动一位，第一个相同的点则是交点。