LeetCode 234. 回文链表 LeetCode

题目描述 【LeetCode 234. 回文链表】请判断一个链表是否为回文链表。
示例1：

输入: 1->2 输出: false

示例2：

输入: 1->2->2->1 输出: true

题解

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public:rd bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL) return true; ListNode* n1 = head; ListNode* n2 = head; while(n2->next != NULL && n2->next->next != NULL) {// 查找中间结点 n1 = n1->next; // n1->中部 n2 = n2->next->next; // n2->结尾 } n2 = n1->next; // n2->右部分第一个结点 n1->next = NULL; // mid->next=NULL ListNode* n3 = NULL; while(n2 != NULL) {// 右半区反转 n3 = n2->next; // n3->保存下一个结点 n2->next = n1; // 下一个反转结点 n1 = n2; // n1移动 n2 = n3; // n2移动 } n3 = n1; // n3->保存最后一个结点 n2 = head; // n2->左边第一个结点 bool res = true; while(n1 != NULL && n2 != NULL) {// 检测回文 if(n1->val != n2->val) { res = false; break; } n1 = n1->next; // 从左到中部 n2 = n2->next; // 从右到中部 } n1 = n3->next; n3->next = NULL; while(n1 != NULL) {// 恢复列表 n2 = n1->next; n1->next = n3; n3 = n1; n1 = n2; } return res; } };