首页 资讯 社群 我的社区 搜索

【数据结构与算法】链表——回文链表

yimo~
2020-05-11 15:26:03

回文链表

LeetCode:回文链表

题目描述:

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

示例:

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

思想:

先用快慢指针取得中间位置的指针,将后半段链表进行翻转,再遍历比较前半段和后半段是否一致。时间复杂度O(3/2n),空间复杂度O(1)

优化:在快慢指针的循环中,同时翻转前半段链表,随后从中间位置往两头遍历,时间复杂度O(n)

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)
            return true;
        ListNode mid=head,end=head;
        while(end!=null&&end.next!=null){
            mid = mid.next;
            end = end.next.next;
        }
        ListNode p=mid,q=mid.next,t;
        while(q!=null){
            t=q.next;
            q.next=p;
            p=q;q=t;
        }
        q=head;
        while(q!=mid){
            if(q.val!=p.val)
                return false;
            q=q.next;
            p=p.next;
        }
        return true;
    }
}

优化版,但是代码着实有点复杂,没有上一种方法直白

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null||head.next==null)
            return true;
        ListNode mid=head,end=head.next,q=head.next,t;
        while(end!=null&&end.next!=null){
            end = end.next.next;
            t = q.next;
            q.next = mid;
            mid = q;q = t;
        }
        ListNode p=(end==null)?mid.next:mid;
        while(q!=null){
            if(q.val!=p.val)
                return false;
            q=q.next;
            p=p.next;
        }
        return true;
    }
}
用户评论