【Leetcode】拿捏链表（三）——CM11 链表分割（牛客）、OR36 链表的回文结构（牛客）

 作者：一个喜欢猫咪的的程序员 

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

---

目录

CM11 链表分割

OR36 链表的回文结构

---

CM11 链表分割

链表分割_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70题目：

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

---

示例：

本题没有示例

---

思路：

本题我们利用两个guard1、guard2带头的链表，将他们合成一个链表来完成。

我们开辟一个链表结构体struct ListNode大小的动态空间n1、n2，将其强制类型转换为结构体指针struct ListNode*来将题目给的链表分为两个小链表。

我们让n1和guard1指向同一块动态空间，n2和guard2也是同理。

我们利用一个cur来遍历原链表，如果val比x小就尾插到第一个链表n1中，负责尾插到第二个链表n2中。

 我们需要额外考虑一种情况，当第二个链表的尾不是原链表的最后一个时，n2的next不为空会出现环装链表的问题，我们需要将n2.next=NULL。

时间复杂度：O（N）                                                             空间复杂度：O（N）

---

代码实现：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* guard1;
        struct ListNode* guard2;
        struct ListNode* cur=pHead;
        struct ListNode* n1;
        struct ListNode* n2;
        n1=guard1=(struct ListNode*)malloc(sizeof(struct ListNode));
        n2=guard2=(struct ListNode*)malloc(sizeof(struct ListNode));
        n2->next=n1->next=NULL;
        while(cur)
        {
            if(cur->val<x)
            {
                n1->next=cur;
                n1=n1->next;
            }
            else
            {
                n2->next=cur;
                n2=n2->next;
            }
            cur=cur->next;
        }
        n1->next=guard2->next;
        n2->next=NULL;
        pHead=guard1->next;
        free(guard1);
        free(guard2);
        return pHead;
    }
};

---

OR36 链表的回文结构

链表的回文结构_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa题目：

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

---

示例:

---

思路：

本题要求我们必须在O（1）的空间复杂度，因此我们不能去开数组，将他们一个个存起来。

我们可以将链表的后半段逆置，然后再将中间节点与头结点的元素做比较，判断是否相等。

这里逆置和查找中间节点的函数可以看一下我的另外2篇博客：

http://t.csdn.cn/82sv7http://t.csdn.cn/82sv7http://t.csdn.cn/HAJ2Ahttp://t.csdn.cn/HAJ2A时间复杂度：O（N）                                                               空间复杂度：O（1）

---

代码实现：

class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode*newhead=reverseList(head->next);
    head->next->next=head;
    head->next=NULL;
    return newhead;
}
struct ListNode* middleNode(struct ListNode* head){
    if(head->next==NULL)
    {
        return head;
    }
    struct ListNode*left=head;
    struct ListNode*right=head;
    struct ListNode*ans=head;
    while(right!=NULL&&right->next!=NULL)
    {
        left=left->next;
        right=right->next->next;
    }
    ans=left;
    return ans;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode*mid=middleNode(A);
        struct ListNode*rhead=reverseList(mid);
        while(A&&rhead)
        {
            if(A->val!=rhead->val)
            return false;
            A=A->next;
            rhead=rhead->next;
        }
        return true;
    }
};

---