234. Palindrome Linked List(Linked List-Easy)

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?

判断一个单链表是否是回文链表。

如:[1, 2, 3, 2, 1] 就是一个回文链表,正着依次看链表中元素和反着依次看链表中元素都是一样的。

解题思路:

  1. 必须做的第一个步骤就是判断输入链表是否为空,或者只有一个元素。如果为空或者只有一个元素,则此链表为回文链表返回true。
  2. 使用快慢指针,找到链表中点。慢指针一次走一步,快指针一次走两步。
  3. 根据找到的链表中点,反转后半部分的链表的所有值,并与整体单链表的值从头依次比对,有一个值不同,则不是回文链表,否则为回文链表。 如输入单链表:[1, 2, 3, 2, 1]

反转后半部分得到的单链表:[1, 2]

Language:C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* pre = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* next = (struct ListNode *)malloc(sizeof(struct ListNode));
    pre=NULL;
    next=NULL;
    while(head!=NULL){
        next=head->next;
        head->next=pre;
        pre=head;
        head=next;
    }
    return pre;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode* slow = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* fast = (struct ListNode *)malloc(sizeof(struct ListNode));
    if(head == NULL || head->next == NULL){
        return true;
    }
    fast = head;
    slow = head;
    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    slow = reverseList(slow->next);
    while(slow){
        if(head->val != slow->val){
            return false;
        }
        head = head->next;
        slow = slow->next;
    }
    return true;
}

Language:cpp

/**
 * 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;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = reverseList(slow->next);
        while(slow){
            if(head->val != slow->val){
                return false;
            }
            head = head->next;
            slow = slow->next;
        }
        return true;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* pre = NULL;
        ListNode* next = NULL;
        while(head!=NULL){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

链表逆序

1.构造5个节点a,b,c,d,e,并对它们进行初始化; 2.将a,b,c,d,e,5个节点连接在一起

1004
来自专栏mukekeheart的iOS之旅

No.002 Add Two Numbers

Add Two Numbers Total Accepted: 160702 Total Submissions: 664770 Difficulty: Med...

2495
来自专栏WD学习记录

LeetCode Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers....

891
来自专栏计算机视觉与深度学习基础

Leetcode 21 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should b...

2109
来自专栏小二的折腾日记

LeetCode-23-Merge-k-Sorted-Lists

这个题乍一看只是对链表的一个排序,因为是很多个链表,所以很简单的想法就是将整个数组里面的两个链表分别进行排序。两个两个互相排序之后就能排好。这里用的是递归。当v...

872
来自专栏计算机视觉与深度学习基础

Leetcode 148 SortList

Sort a linked list in O(n log n) time using constant space complexity. 链表排序,n...

1997
来自专栏计算机视觉与深度学习基础

Leetcode 82 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leavi...

2025
来自专栏LeetCode

LeetCode 206. Reverse Linked List

1052
来自专栏深度学习与计算机视觉

数据结构-单链表的读取,插入与删除

链表定义: struct ListNode { int value; ListNode *next; }; 单链表读取 在顺序存储结构中,比如数组中,想...

2207
来自专栏LeetCode

LeetCode 2 & 455 Add Two Numbers I&II

You are given two non-empty linked lists representing two non-negative integers....

900

扫码关注云+社区

领取腾讯云代金券