链表中的倒数第k个结点 合并两个链表 分割链表 链表的回文结构

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead==NULL||(k<=0))//如果为空链表或者k是<=0,直接返回NULL
    {
        return NULL;
    }
    struct ListNode*ret=pListHead;
    struct ListNode*tail=pListHead;
    //后指针先走k-1步
    while((--k)&&tail)//细节,k--和--k的区别
    {
        tail=tail->next;
    }
    //k太大
    if (tail == NULL)//如果指向的就是最后一个节点的后的NULL,即k太大
    {
        return NULL;
    }
    //两个指针一起走
    while(tail->next!=NULL)
    {
        tail=tail->next;
        ret=ret->next;
    }
    return ret;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //创建带哨兵卫的结点
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    phead->next = NULL;
    struct ListNode* ret = phead;//保存这个哨兵卫结点
    while (list1 && list2)
    {
        if (list1->val < list2->val)//谁小谁尾插
        {
            phead->next = list1;
            phead = phead->next;
            list1=list1->next;
        }
        else
        {
            phead->next = list2;
            phead = phead->next;
            list2=list2->next;
        }
    }
    //如果一方为空的情况
    if (list1 == NULL)
    {
        phead->next = list2;
    }
    if (list2 == NULL)
    {
        phead->next = list1;
    }
    return ret->next;//哨兵卫结点的next
}

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
    //创建两个链表的头结点
    ListNode* SmallHead=(ListNode*)malloc(sizeof(ListNode));
    ListNode* BigHead=(ListNode*)malloc(sizeof(ListNode));
    //代替两个头结点遍历的指针
    ListNode* SmallTail= SmallHead;
    ListNode* BigTail= BigHead;
    //遍历现有链表
    while(pHead)
    {
        //小的尾插到小的链表中
        if(pHead->val<x)
        {
            SmallTail->next=pHead;
            SmallTail=SmallTail->next;
        }
        else {//大的尾插到大的链表中
            BigTail->next=pHead;
            BigTail=BigTail->next;
        }
        pHead=pHead->next;
    }
    //链接
    SmallTail->next=BigHead->next;
    //大链表的尾结点不一定是NULL,我们要置NULL
    BigTail->next=NULL;
    //保留要返回的头指针
    pHead=SmallHead->next;
    //释放自己动态内存申请的空间
    free(SmallHead);
    free(BigHead);
    return pHead;
    }
};

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
       //寻找中间结点
        ListNode* mid=middleNode(A);
        //反转链表后半段
        ListNode* B=reverseList(mid);
        //比较
        while(A&&B)
        {
            if(A->val!=B->val)
            {
                return false;
            }
            A=A->next;
            B=B->next;
        }
        return true;
    }
};