分割链表和回文链表习题

感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

个人主页：LaNzikinh-CSDN博客

收入专栏:初阶数据结构_LaNzikinh篮子的博客-CSDN博客

---

一.回文链表LCR 027. 回文链表 - 力扣（LeetCode）

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]输出: true

示例 2：

输入: head = [1,2]输出: false

思路：先找到中间结点，然后逆置，逆置完后在进行比较，比较完后如果一直相等，那就正确，不相等那就错误奇数偶数一样

偶数

奇数

之前写过一个反转链表的代码http://t.csdnimg.cn/tcPai，这次就来教一下如何求链表的中间节点，就是快慢指针的思想，快的走两步，慢的走一步

struct ListNode*mid(struct ListNode*head)
{
struct ListNode*slow.*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}

实现

bool isPalindrome(struct ListNode* head) 
{
	//求中间结点
	struct ListNode* mid = midd(head);
	//中间结点逆置
	struct ListNode* rhead = rereverList(mid);
	//两个链表判断
	struct ListNode* curA = head;
	struct ListNode* curB = rhead;
	//一个结束就停止循环
	while (curA && curB)
	{
		//不相等就停
		if (curA->val != curB->val)
			return false;
		//相等就继续走
		else
		{
			curA = curA->next;
			curB = curB->next;
		}
	}
	return true;
}

二.分割链表面试题 02.04. 分割链表 - 力扣（LeetCode）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 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]

思路：开哨兵为的头节点，搞两个链表在合并

但是注意！！！存在问题，因为之前可能已经有连好的存在，所以最后还要解开

struct ListNode* partition(struct ListNode* head, int x)
{
	struct ListNode* LessHead, * LessTail, * greaterHead, * greatertail;
	//开辟哨兵位的头结点
	LessHead = LessTail = (struct ListNode*)malloc(sizeof(struct ListNode*));
	greaterHead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode*));
	LessTail->next = NULL;
	greatertail->next = NULL;
	struct ListNode* cur = head;
	//当cur走完，循环停止
	while (cur)
	{
		//如果小，放入less链表中
		if (cur->val < x)
		{
			LessTail->next = cur;
			LessTail = cur;
		}
		//如果大于等于，放入greater链表中
		else
		{
			greatertail->next = cur;
			greatertail = cur;
		}
		cur = cur->next;
	}
	//最后把链表合并
	LessTail->next = greaterHead->next;
	//解开已经有连好的存在
	greatertail = NULL;
	//存储哨兵位前的元素，释放哨兵位的头结点
	struct ListNode* newhead = LessHead->next;
	free(LessHead);
	free(greaterHead);
	return newhead;
 
}