首页 > 代码库 > 234. Palindrome Linked List
234. Palindrome Linked List
- Total Accepted: 88244
- Total Submissions: 277193
- Difficulty: Easy
- Contributors: Admin
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
来源: https://leetcode.com/problems/palindrome-linked-list/?tab=Description
分析
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public : bool isPalindrome(ListNode* head) { if (head == NULL || head->next == NULL) return true ; //use slow and fast pointer to find the mid node ListNode* slow = head, * fast = head; while (fast && fast->next && fast->next->next){ slow = slow->next; fast = fast->next->next; } //reverse the right half list ListNode* l1 = head; ListNode* l2 = slow->next; slow->next = NULL; l2 = reverse(l2); //compare the two lists‘s node vale while (l2){ if (l1->val != l2->val) return false ; l1 = l1->next; l2 = l2->next; } return true ; } ListNode* reverse(ListNode* head){ ListNode* pre = NULL; ListNode* cur = head; while (cur){ ListNode* tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; } }; |
null
234. Palindrome Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。