程序员面试金典-面试题02.06-回文链表

迈不过友情╰ 2022-12-28 00:45 135阅读 0赞

## 程序员面试金典-面试题02.06-回文链表 ##

编写一个函数，检查输入的链表是否是回文的。
    
     
    
    示例 1：
    
    输入： 1->2
    输出： false 
    示例 2：
    
    输入： 1->2->2->1
    输出： true 
     
    
    进阶：
    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/palindrome-linked-list-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.将数据读入数组
    2.使用前后指针，若值相等，指针朝中间走；
    			   若不相等，break，返回不为回文

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    bool isPalindrome(struct ListNode* head){
        
        if(head == NULL)
            return true;
        struct ListNode * ptr = head;
        int num = 0;
        while(ptr != NULL)
        {
        
            num++;
            ptr = ptr->next;
        }
        int data[num];
        ptr = head;
        for(int i=0;i<num;i++)
        {
        
            data[i] = ptr -> val;
            ptr = ptr -> next;
        }
        int start = 0;
        int rear = num-1;
        int is_Palin = 1;
        while(start < rear)
        {
        
            if(data[start] != data[rear])
            {
        
                is_Palin = 0;
                break;
            }
            else
            {
        
                start++;
                rear--;
            }
        }
        if(is_Palin == 1)
            return true;
        else
            return false;
    }