LeetCode – Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

目录隐藏

1 解题：

2 实现：

解题：

找到中间节点后反转判断节点回文

实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){

        if (head == NULL || head->next == NULL) {
            return true;
        }
        struct ListNode* slow=head;
        struct ListNode* fast=head;
        struct ListNode* pre=NULL;
        struct ListNode* next=NULL;
  
    
        //get middle
        while(  fast!=NULL && fast->next!=NULL){
             slow = slow->next;
             fast = fast->next->next;               
        }
        if(fast) {
                 slow=slow->next;
        }
    
        struct ListNode* cur=slow;
        //and reverse 
        while(cur!=NULL){
            pre = cur;
            cur = cur->next;
            pre->next = next;
            next = pre;
        }
        //compare 
        cur = head;
        while(pre!=NULL){
               //printf("%d %d\n", head->val, pre->val);
               if (cur->val != pre->val){
                     return false;
               }
               cur=cur->next;
               pre= pre->next;
        }

        return true;

}

LeetCode – Palindrome Linked List

解题：

实现：

garlic

Be First to Comment

发表回复