牛客——OR36 链表的回文结构（C语言，配图，快慢指针）

       

目录

思路一：链表翻转

思路二：快慢指针，分别从头和尾间开始比较

---

        本题是没有对C的支持的，但因为CPP支持C，所以这里就用C写了，可以面向更多用户

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

思路一：链表翻转

        简单的想想整形我们怎么比较，就是将整形A 依次取尾，放到整形B中。

int a = 121;
int t = a;
int b = 0;
while(t)
{int temp = t % 10;b = b*10+temp;t /= 10;
}
if(b == a)
{printf("Yes");
}

        这里我们也借用这个思路，先遍历一遍链表，取出每个节点的val，放到整形A中，在将链表翻转，再次取出每个节点的val,放到整形B中，进行比较。

struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereint ret1 = 0;   //原链表int ret2 = 0;struct ListNode* n1 = NULL;struct ListNode* n2 = A;struct ListNode* n3 = A->next;while(n2){ret1 = ret1 * 10 + n2->val;n2->next = n1;n1 = n2;n2 = n3;n3 = n3->next;}while(n1){ret2 =ret2* 10 + n1->val;n1 = n1->next;}if(ret1 == ret2){return true;}return false;}
};

思路二：快慢指针，分别从头和尾间开始比较

        这里的思路，是在思路一的基础上，在进了一步，让链表从中间到尾进行翻转，进行比较。

struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList {
public://找出中间节点ListNode* MiddleList(ListNode* phead){ListNode* fast = phead;ListNode* slow = phead;while(fast && fast->next){fast = fast->next->next;slow=slow->next;}return slow;}//将中间节点到尾节点逆置ListNode* ReverseList(ListNode* phead){ListNode* n1 = NULL;ListNode* n2 = phead;ListNode* n3 = phead->next;while(n2){n2->next = n1;n1 =n2;n2 =n3;n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* phead) {// write code hereListNode* mid = MiddleList(phead);ListNode* rev = ReverseList(phead);ListNode* cur =phead;while(cur && rev){if(cur->val != rev->val){return false;}cur =cur->next;rev =rev->next;}return true;}
};