注意OJ题，传过来的一般是指向头结点的头指针，而非带哨兵卫的头结点。

---

一.移除链表元素

解题思路1：不建立哨兵卫

（1）着重利用到两个指针，cur（即当前位置，去寻找值为val的重要指针），prev（指向cur前面的一个结点），利用这两个指针移除链表中的特定元素。
（2）刚开始cur指向头结点，而prev被初始化为NULL（不然就会沦为野指针），cur会在每次循环后，遍历移向下一个结点，所以当cur为NULL时，跳出循环，如果cur指向的结点值不为val，则cur跳过此结点，指向下一个结点，在这步指向之前，要把cur的位置先赋给prev。
（3）当cur指向的结点值为val，则要删除当前结点。在这里分为两种情况，要删除的是头结点，和不是头结点。如果是头结点，第一步替换头结点，head=head->next;第二步：释放头结点，free（cur），第三步：重置cur，cur=head。如果不是头结点，第一步断开连接，让prev->next=cur->next,第二步释放次结点，free(cur),第三步cur指向此节点的下一个结点，即cur=prev->next;
>图解：

代码实现：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur=head,*prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
           //1.头删
           if(cur==head)
           {
                head=head->next;
                free(cur);
                cur=head;
           }
           //2.非头删
           else
           {
               prev->next=cur->next;
               free(cur);
               cur=prev->next;
           }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

解题思路2：建立新链表

解题思路：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur=head;
    struct ListNode* newhead=NULL,*tail=NULL;

    while(cur)
    {
        if(cur->val!=val)
        {
            if(tail==NULL)
            {
                newhead=tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
            cur=cur->next;
        }
        else
        {
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
    }
    //最后一个结点为val时，注意将最后一个结点的指针域指向空
    if(tail)
    {
        tail->next=NULL;
    }
    return newhead;
}

解题思路3：建立哨兵卫

带哨兵卫后（头结点，但只有指针域），代码变得更加简洁，建立新链表时，不需要判断tail是否为NULL，让tail=guard后，即可连接符合条件的结点。一定要记住，若最后一个结点为val，要记住把tail->next==NULL。
*注意我们建立的新节点最后也需要释放。并且最开始要把guard->next置为空，不然它将会是一个野指针，当传过来的是空链表，那么程序就会报错。

struct ListNode* removeElements(struct ListNode* head, int val)
{
   struct ListNode* cur=head;//cur勇于遍历原链表
   struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
   guard->next=NULL;//若原链表为NULL
   struct ListNode* tail=guard;//tail指向头结点

   while(cur)
   {
       if(cur->val!=val)
       {
           tail->next=cur;//连接符合条件的结点
           tail=tail->next;//更新tail
           cur=cur->next;//更新cur
       }
       else
       {
           struct ListNode* del=cur;//保存val的位置
           cur=cur->next;
           free(del);
       }
   }
   //最后结点为val
   if(tail)
   {
       tail->next=NULL;
   }
   head=guard->next;
   free(guard);
   return head;
}

二.合并两个有序链表

解题思路：创建新的链表
（1）两个指针分别遍历两个链表
（2）建立哨兵卫，tail尾指针，cur->val较小值进行连接，注意指针指向的更新。
（3）注意有一个有序链表会先连接完成，那么会退出循环，注意我们还需要将剩下一个链表的其余结点连接上去
（4）注意释放哨兵卫的头结点
（5）若传过来的是空链表，那么刚开始我们要把guard->next置为空，不然它将沦为野指针。
（6）这里因为原链表最后已置为空，不像上道题目一样，可能会把最后一个结点删除，所以我们不用考虑这层。

代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* guard=(struct ListNode* )malloc(sizeof(struct ListNode));
    guard->next=NULL;

    struct ListNode* cur1=list1,* cur2=list2;
    struct ListNode* tail=guard;


    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next=cur1;
            cur1=cur1->next;
        }
        else
        {
            tail->next=cur2;
            cur2=cur2->next;
        }
        tail=tail->next;
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    struct ListNode* head=guard->next;
    free(guard);
    return head;
}

三.翻转链表

解题思路1：头插

（1）定义一个新的指针newnode,进行头插，注意更新头指针。
（2）两个指针cur，next，用于前后遍历原链表，next指针用于保存cur下一个结点的位置，cur是要进行头插的结点。注意每次循环都要更新这两个指针的位置。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newnode = NULL;

    while(cur)
    {
        struct ListNode* next=cur->next;//保留cur下一个结点的地址
        cur->next=newnode;
        newnode=cur;

        cur=next;
    }
    return newnode;
}

解题思路2：翻转

（1）需要3个辅助指针，当n2指向NULL时跳出循环；
（2）三个指针进行迭代
（3）注意传过来的若为空指针，n3不能直接置成，n3=n2->next,这是错误的示范。所以要先判断n2是否为NULL。

struct ListNode* reverseList(struct ListNode* head)
{
   struct ListNode* n1,*n2,*n3;
   n1=NULL;
   n2=head;
   n3=NULL;

   while(n2)
   {
       n3=n2->next;
       n2->next=n1;
       
       //迭代
       n1=n2;
       n2=n3;
   }
   return n1;
}

四.链表的中间结点

解题思路1：遍历
因为这道题目没有时间复杂度的要求，所以要解决这道题，我们只需要先遍历一遍链表，统计链表的结点个数，然后再遍历一遍链表，寻找中间结点即可。此方法的时间复杂度为o(n^2)。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* cur=head;
    int count=0;

    while(cur)//遍历链表
    {
        count++;
        cur=cur->next;
    }
    int mid=count/2;
    struct ListNode* midnode=head;
    while(mid--)
    {
        midnode=midnode->next;
    }
    return midnode;
}

解题思路2：快慢指针

我们也可以只遍历一遍链表，就找到中间结点，这样时间复杂度就为O(n).
利用的方法是快慢指针。那么什么是快慢指针呢？
快指针一次走两步，慢指针一次走一步，那么当快指针走到空时，慢指针走到一半，之后返回慢指针指向的地址即可。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast,*slow;
    fast=slow=head;

    while(fast&&fast->next)
    {
        slow=slow->next;//慢指针走一步
        fast=fast->next->next;//快指针走两步
    }
    return slow;
}

五.链表中倒数第k个结点

要求只遍历一遍，即时间复杂度为O(n).
方法：利用快慢指针
fast先走k步

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* fast,*slow;
    fast=slow=pListHead;
    //while(--k)// k-1步
    while(k--)//k步
    {
        //1.传过来的是空链表
        //2.k>=结点数
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

六.链表分割

测试用例：

（1）普通情况

（2）当最后一个小于x时，会造成环状，最后返回的是val4这个结点，所以val7的结点一定要置为空

（3）当传过来的为空指针，我们的输出也为{}空，所以防止 lessTail->next=greaterGuard->next;出错，我们一开始得把新建的两个哨兵卫结点的next置NULL

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* lessGuard,*lessTail,*greaterGuard,*greaterTail;
        lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterGuard=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        //注意置空
        lessGuard->next=NULL;
        greaterGuard->next=NULL;
        
        //cur遍历原链表
        struct ListNode* cur=pHead;
        
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;//连接符合条件的cur
                lessTail=lessTail->next;//更新指针
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            cur=cur->next;
      }
      //连接俩链表
        lessTail->next=greaterGuard->next;
        greaterTail->next=NULL;
        
        pHead=lessGuard->next;
        free(greaterGuard);
        free(lessGuard);
        
        return pHead;
     }
};

七.链表的回文结构

测试用例：

class PalindromeList {
public:
   
    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* slow,*fast;
        slow=fast=head;
        
        while(fast&&fast->next)
        {
            slow=slow->next;//走一步
            fast=fast->next->next;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* n1,*n2,*n3;
        n1=NULL;
        n2=head;
        n3=NULL;
        while(n2)
        {
            n3=n2->next;
            n2->next=n1;
            
            //迭代
            n1=n2;
            n2=n3;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* head)
    {
        //1.找中间结点
        struct ListNode* mid=middleNode(head);
        //2.逆序包括中间结点在内之后的结点
        struct ListNode* rmid=reverseList(mid);
        
        while(head&&rmid)
        {
            //判断回文
            if(head->val!=rmid->val)
            {
                return false;
            }
            head=head->next;
            rmid=rmid->next;
        }
        return true;
    }
};

八.相交链表

1.思路：想找到俩链表相交的结点，即需要俩链表的最后一个结点的next指针域指向的结点地址相同；（注意而非val相同）
2.要求：时间复杂度为O(n+m),空间复杂度为O(1);
3.方法：（1）是否相交->俩链表的尾结点是否相等；
（2）求出俩链表的长度lenA，lenB
（3）较长的链表先走 差距步 ，然后再俩链表同时走，第一个结点地址相等，那就是链表交点。
（4）注意空链表无结点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1;
    int lenB=1;
    //计算链表长度，找到尾结点
    while(curA)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB)
    {
        curB=curB->next;
        lenB++;
    }
    //如果俩链表遍历到最后的结点地址不相同
    //则两链表不相交
    if(curA!=curB)
    {
        return NULL;
    }
    struct ListNode* shorttail=headA;
    struct ListNode*longtail=headB;
    if(lenA>lenB)
    {
        shorttail=headB;
        longtail=headA;
    }
    //先走差距步
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longtail=longtail->next;
    }
    
    while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
    {
        if(longtail==shorttail)//相等时返回结点
        {
            return shorttail;
        }
        else
        {
            longtail=longtail->next;
            shorttail=shorttail->next;
        }
    }
    return NULL;
}

九.环形链表I

注意环形链表不能遍历

测试用例：

解题思路1：

方法：快慢指针
fast指针一次走两步，slow指针一次走一步

代码实现：

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast,*slow;
    //1.快慢指针指向头结点
    fast=slow=head;
    //2.追赶
    //因为fast走的比slow快
    //若有环则循环
    //若无环fast会先指向NULL，跳出循环
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        //慢指针一次走一步
        //快指针一次走两步
        //走一次，差距缩小一步
        //直到相遇
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

思考问题1:

（1）请问，slow一次走一步，fast一次走三步，是否可以？
假设slow进环后，fast和slow之间差距N，那么追赶的距离就是N；
这种情况下，每追赶一次，他们之间的距离就缩小2步。·如果追赶的距离N是偶数，就追得上；
若N是奇数，意味着fast与slow，在第一次中，不会刚好相遇，会出现以下这种情况，于是他们之间的距离就变成了C-1(C是环的长度)，并进入新一轮的追赶，在这种情况下，若C-1是偶数，则这一轮追得上，若C-1是奇数，则永远追不上。

（2）请问，slow一次走一步，fast一次走X步，是否可以？
（3）请问，slow一次走Y步，fast一次走X步（X>Y）,是否可以？
与上面的情况同理，能否追赶上取决于，每追赶一次，slow和fast指针的距离是缩小偶数倍，还是奇数倍，并且取决于环的长度。

十.环形链表II

这道题与上道题大近相同，这道题要判断链表是否有环，还需要返回链表开始入环的第一个结点（即L的位置）,如果链表无环，则返回NULL。

解题思路1：公式推导

由上述环状链表可得，fast快指针一次走两步，slow一次走一步，所以得出公式：fast走的距离=2*slow走的距离。
（1）假设进环前的长度是L，环的长度是C，入口点到相遇点距离是X
（2）则slow走的距离是：L+X；fast走的距离是：L+N*C+X;（假设slow进环，fast在环里面已经转了N圈，N>=1）
（3）推导公式：
2(L+X)=L+NC+X
L+X=NC
L=NC-X
L=(N-1)C+C-X
可以这么说：一个指针A从头开始走，一个指针B从相遇点开始走，他们会在入口点相遇

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow, *fast;
    slow=fast=head;

    while(fast&&fast->next)//若为空，则无环
    {
        slow=slow->next;
        fast=fast->next->next;
        //直到相遇
        if(slow==fast)
        {
            struct ListNode* meet=slow;
            //一个指针从头开始走，一个指针从相遇点开始走
            //他们会在入口点相遇
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return head;//or meet
        }
    }
    return NULL;
}

解题思路2：转换成相交问题

1.找到交点(slow==fast);
2.保留链表交点下一个结点的地址
3.断开链表
4.找链表交点
5.恢复链表

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1;
    int lenB=1;
    //计算链表长度，找到尾结点
    while(curA)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB)
    {
        curB=curB->next;
        lenB++;
    }
    //如果俩链表遍历到最后的结点地址不相同
    //则两链表不相交
    if(curA!=curB)
    {
        return NULL;
    }
    struct ListNode* shorttail=headA;
    struct ListNode*longtail=headB;
    if(lenA>lenB)
    {
        shorttail=headB;
        longtail=headA;
    }
    //先走差距步
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longtail=longtail->next;
    }
    
    while(longtail&&shorttail)//俩链表一起走的时候，保证不为空
    {
        if(longtail==shorttail)//相等时返回结点
        {
            return shorttail;
        }
        else
        {
            longtail=longtail->next;
            shorttail=shorttail->next;
        }
    }
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast, *slow;
    fast=slow=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        {
            //相遇点
            struct ListNode* meet=slow;
            //保存相遇点的下一个结点
            struct ListNode* next=meet->next;
            //断开环
            meet->next=NULL;

            //恢复环
            struct ListNode* entryNode=getIntersectionNode(next,head);//找交点
            meet->next=next;
            return entryNode;

        }
    }
    return NULL;
}