分割链表 | 链表的回文结构

1.分割链表＜难度系数⭐⭐＞

📝 题述：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序 (相对顺序不变)，返回重新排列后的链表的头指针。

💨 示例1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

💨 示例2：
输入：head = [2,1], x = 2
输出：[1,2]

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
思路，双链表，比x小的尾插至一个链表中，比x大的尾插至另一个链表中。最后再链接两链表

leetcode原题
牛客网原题

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

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* partition(struct ListNode* head, int x)
{
	struct ListNode *SmallHead, *BigHead, *SmallTail, *BigTail;
    //开辟二个节点
    SmallHead = SmallTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    BigHead = BigTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    //拷贝头节点
    struct ListNode* cur = head;
    //大小分类
    while(cur)
    {
    	if(cur->val < x)
        {
        	SmallTail->next = cur;
            SmallTail = cur;
        }
        else
        {
        	BigTail->next = cur;
            BigTail = cur;
        }
            cur = cur->next;
    }
	//再将最后一个节点这里置为空尤为重要，否则可能会造成死循环
	BigTail->next = NULL;
	//链接二节点
	SmallTail->next = BigHead->next;
	struct ListNode* temp = SmallHead->next;
	free(SmallHead);
	free(BigHead);
	
	return temp;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 6;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 3;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 4;

	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n6->val = 5;

	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n7->val = 6;

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

	partition(n1, 3);
	return 0;
}

2.链表的回文结构＜难度系数⭐⭐＞

📝 题述：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

💨 示例1：
输入：head = [1,2,2,1]
输出：true

💨 示例2：
输入：head = [1,2,3,2,1]
输出：true

💨 示例3：
输入：head = [1,2]
输出：false

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
思路一， 钻牛角尖，使用数组 (OJ能过，但面试官不能过)。

这里需要注意的是， 有些OJ题目，有时间复杂度和空间复杂度的要求，但是平台并不能很好的检查两者的参数，因为有很多客观存在的因素，所以并不能制定一个公平的规则，这也是目前牛客网需要去改进的地方。
但相比牛客网leetcode会严格些，包括测试用例的完整度，但也不能只用leetcode，因为就目前来看，大多数的笔试环境用的都是牛客。
(从这道题就可以看出时间复杂度为是符合要求的，但是空间复杂度不符号要求，且牛客网能跑的过去)

思路二， 逆置后半部分再比较。

牛客原题

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

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路一
bool chkPalindrome1(ListNode* phead)
{
	int a[900];
	struct ListNode* cur = phead;
	int n = 0;
	//将链表中的val拷贝至a数组
	while(cur)
	{
		a[n++] = cur->val;
		cur = cur->next;
	}
	//判断回文 
	int left = 0, right = n - 1;
	while(left < right)
	{
		if(a[left] != a[right])
		{
			return false;
		}
            left++;
            right--;
        }
        return true;
    }
}
struct ListNode* FindMidNode(struct ListNode* phead)
{
	//通过快慢指针查找中间节点
	struct ListNode *slow, *fast;
	slow = fast = phead;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}
struct ListNode* reverseList(struct ListNode* pmid)
{
	//使用头插逆置
	struct ListNode* cur = pmid;
	struct ListNode* newhead = NULL;
	while (cur)
	{
		struct ListNode* next = cur->next;
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	return newhead;
}
//思路二
bool chkPalindrome2(struct ListNode* A)
{
	struct ListNode* mid = FindMidNode(A);
	struct ListNode* rHead = reverseList(mid);
	struct ListNode* cur = A;
	while (rHead && cur)
	{
		if (rHead->val != cur->val)
			return false;
		rHead = rHead->next;
		cur = cur->next;
	}
	return true;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 2;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 1;


	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	isPalindrome1(n1)
	isPalindrome2(n1)
	return 0;
}