数据结构-->单链表OJ题--->讲解_05

本期我们讲解 :>

1.给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

本题的思路是 创建两个链表，通过比较，一个存放小于x的结点的链表，另一个存放大于或等于x的结点的链表！！

最后再将两个链表链接起来即可！！

直接上手代码 :>

/*
typedef int SLTDataType;

typedef struct listNode
{
	SLTDataType val;
  struct listNode* next;
  
}SLTNode;
*/

SLTNode* partition(SLTNode* phead, int x)
{
	SLTNode* cur = phead;
  SLTNode* small_head, small_tail, max_head, max_tail;
  
  small_head = small_tail = (SLTNode*)malloc(sizeof(SLTNode));
  max_head = max_tail = (SLTNode*)malloc(sizeof(SLTNode));
  
  while(cur)
  {
  	if(cur ->val < x)
    {
 				small_tail ->next = cur;
        small_tail = cur;
    }
    else
    {
    	max_tail ->next = cur;
      max_tail = cur;
    }
    cur = cur ->next;
  }
  
  
	//进行长短链表链接
  small_tail ->next = max_tail ->next;
  max ->next = NULL;
  
  free(small_head);
  free(max_head);			//防止内存泄露
  
  return small_head ->next;
}

2.链表的回文结构

何为回文结构呢？

---->关于中间结点对称即可

如，1 -> 2  ->2  -> 1 即是回文结构

显然是要判断真假，因此用布尔判断！！

现在讲解思路 :>

1.先找到中间结点

2.将中间结点之后的链表进行反转

3.对比中间结点之前的链表与反转之后的那部分链表

现在上手代码 :>

//寻找中间结点
SLTNode* MidNode(SLTNode* phead)
{
	SLTNode* slow = phead;
  SLTNode* fast = phead;		//快慢指针的思想，绝对强
  
  while(fast && fast >next)
  {
  	slow = slow ->next;
    fast = fast ->next ->next;
  }
  return slow;
}

//反转单链表
SLTNode* reverseNode(SLTNode* phead)
{
	SLTNode* cur = NULL;
  SLTNode* prev = phead;
  while(cur)
  {
  	SLTNode* tamp = prev ->next;
    prev ->next = cur;
    cur = prev;
    prev = tamp;
  }
  return prev;
}

//布尔判空
bool palindrome(SLTNode* phead)
{
	//寻找中间结点
  SLTNode* mid = MidNode(phead);
  //反转链表
  STNode* rhead = reverseNode(mid);
 
  while(head && rhead)
  {
  	if(phead ->val != rphead)
    {
      return false;      
    }
    phead = phead ->next;
    rphead = rphead ->next;
  }
  return true;
}

老铁们，以上代码的书写，是不是特别六！！

其实，当个CV工程师还是蛮好的！！以前的知识不就现在派上用场了吗！！而且这种代码风格，其实是蛮好的！！

比得上那些只用一个函数搞定，在逻辑上，更容易让人理解和接收！！

本期讲解就到这里了！！感谢支持！！感谢阅读！！