1.顺序表和链表打印断言

顺序表定义：SeqList Sq;
在传给打印函数的时候:SeqListPrint(&Sq)
在函数内部的时候&Sq一定不为空，void SeqListPrint(SeqList* ps)所以要断言一下assert(ps);

单链表定义变量: SLTNode* phead;
在传给打印函数的时候:SLTNodePrint(&phead);
在函数内部打印的时候phead为空的时候，&phead也可能为空，所以不能断言

2.栈（错）和堆上（对）定义一个新节点

void SLTNodePushFront(SLTNode** pphead,STDateType x)
{
   //错误示范：栈上开辟的，出函数销毁
   SLTNode newnode;

   //正确做法：malloc结点，堆上开辟，空间需要手动释放
   SLTNode* newhead=(SLTNode*)malloc(sizeof(SLTNode));
}

3.二级指针

以尾插函数为例，如果主函数里的plist为空，那么要改plist就要传二级指针
但是为什么在plist不为空的时候，要尾插一个

void SLTNodePushBack(SLTNode* pphead, SLTDateType x)//1
{
	assert(pphead);//2

	SLTNode* newhead = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->next = NULL;
	newnode->date = x;

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail)
		{
			tail = tail->next;
		}
		tail->next = newnode;//3
	}
}

#define _CRT_SECURE_NO_WARNINGS 1

struct  ListNode
{
	int val;
	struct ListNode* next;
};

#include<stdio.h>
#include<stdlib.h>


int main()
{
	struct  ListNode* n1 = (struct  ListNode*)malloc(sizeof(struct  ListNode)); 
	struct  ListNode* n2 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
	struct  ListNode* n3 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
	struct  ListNode* n4 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
	struct  ListNode* n5 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
	struct  ListNode* n6 = (struct  ListNode*)malloc(sizeof(struct  ListNode));
	struct  ListNode* n7 = (struct  ListNode*)malloc(sizeof(struct  ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;
	n7->val = 7;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = NULL;

	return 0;
}

class PalindromeList {
public:
    bool chkPalindrome(ListNode* phead) {
        // 第一步：快慢指针求中间结点slow
        struct ListNode* fast,*slow;
        fast=slow=phead;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        //第二步:部分反转,得新头结点prev
        struct ListNode* prev=NULL;
        struct ListNode* cur=slow;
        while(cur)
        {
            struct ListNode* next=cur->next;
            
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        //第三步：判断新旧链表是否相等
        struct ListNode* newhead=prev;
        struct ListNode* oldhead=phead;
        while(newhead)
        {
            if(newhead->val!=oldhead->val)
            {
                return false;
            }
            newhead=newhead->next;
            oldhead=oldhead->next;
        }
        return true;
    }
};

class PalindromeList {
public:
    //动态开辟一个新节点，新节点的值为cur->val
    struct ListNode* BuySListNode(int val)
    {
        struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->val=val;
        newnode->next=NULL;
        return newnode;
    }
    
    bool chkPalindrome(ListNode* phead) {
        //第一步：拷贝原链表，得到copyhead
        struct ListNode* Guard,*Tail;
        Guard=Tail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=phead;
        while(cur)
        {
            struct ListNode* next=cur->next;
            
            struct ListNode* newnode=BuySListNode(cur->val);

            Tail->next=newnode;
            Tail=Tail->next;
            cur=next;
        }
        struct ListNode* copyhead=Guard->next;
        free(Guard);
        Guard=NULL;
        
        //第二步：将原链表整体反转,得到reversehead
        struct ListNode* prev=NULL;
        struct ListNode* cur2=phead;
        while(cur2)
        {
            struct ListNode* next=cur2->next;
            cur2->next=prev;
            prev=cur2;
            cur2=next;
        }
        struct ListNode* reversehead=prev;
        
        //第三步：遍历判断两个链表是否值相等
        while(copyhead)
        {
            if(copyhead->val!=reversehead->val)
            {
                return false;
            }
            copyhead=copyhead->next;
            reversehead=reversehead->next;
        }
        return true;
    }
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //第一步：分别遍历两个链表，分别求出两个链表的长度
    int lenA=1,lenB=1;
    struct ListNode* TailA=headA;
    struct ListNode* TailB=headB;
    while(TailA->next)
    {
        ++lenA;
        TailA=TailA->next;
    }
    while(TailB->next)
    {
        ++lenB;
        TailB=TailB->next;
    }
    if(TailA!=TailB)
    {
        return false;
    }

    //第二步：让长度长的那个链表先走两链表长度的差距步
    struct ListNode* longhead=headA;
    struct ListNode* shorthead=headB;
    if(lenA<lenB)
    {
        longhead=headB;
        shorthead=headA;
    }
    int div=abs(lenA-lenB);
    struct ListNode* cur1=longhead;
    struct ListNode* cur2=shorthead;
    while(div--)
    {
        cur1=cur1->next;
    }

    //第三步：短链表从头开始走，长链表从差距步开始同步走
    while(cur1!=cur2)
    {
        cur1=cur1->next;
        cur2=cur2->next;
    }
    //第四步：相遇点即是相交链表的交点结点，返回
    return cur1;
}

class Partition {
public:
    ListNode* partition(ListNode* pHead, int val) {
        // write code here
        //第一步：定义大小Guard和Tail指针
        struct ListNode* lessGuard,*lessTail;
        lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lessGuard->next=NULL;
        struct ListNode* bigGuard,*bigTail;
        bigGuard=bigTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        bigGuard->next=NULL;
        
        //第二步:   遍历尾插到相应新链表
        struct ListNode* cur=pHead;
        while(cur)
        {
            struct ListNode* next=cur->next;
            if(cur->val<val)
            {
                lessTail->next=cur;
                lessTail=lessTail->next;
            }
            else 
            {
                bigTail->next=cur;
                bigTail=bigTail->next;
            }
            cur=next;
        }
        //第三步： 连接两个分割的链表
        lessTail->next=bigGuard->next;
        bigTail->next=NULL;
        struct ListNode* newhead=lessGuard->next;
        free(lessGuard);
        free(bigGuard);
        lessGuard=NULL;
        bigGuard=NULL;
        return newhead;
        
    }
};