算法-判断回文链表

1,831 阅读3分钟

关键词: leetcode 234题 回文链表

回文数

中文里,有回文诗句、对联,如:"灵山大佛,佛大山灵","客上天然居,居然天上客"等等,都是美妙的符合正念倒念都一样的回文句. 回文数则是有类似22、383、5445、12321,不论是从左向右顺读。

创建链表

因为js没有链表这种数据结构,要做这道题先来声明一个链表节点对象。还记得链表有哪些特性吗?用一张图来表示就是这样。

链表节点对象

function ListNode(x){
    this.val = x; // 数据域
    this.next = null; // 指针域
}

要实现A->B->C, 把下一个节点赋值给当前对象的next属性,通过这样的方式连接。当然也可以再增加个自动的方法。

var head = new ListNode('A');
var second = new ListNode('B');
head.next = second; 
var third = new ListNode('C');
second.next = third;

在JS中,this.val代表当前节点的值,this.next指向下一个节点,若this.next为null(对象),则说明该节点为链表的最后一个节点。

打印链表中的值,知道了链表和数组的关系,后面用数组来替换链表,这样比较好写代码。

function printListFromTailToHead(head)
{
    let arr = [];
    let start = head;
    while(start){
        arr.push(start.val);
        start = start.next;
    }
    arr // ['A','B','C']
    return arr.reverse(); // ['C','B','A']
}

判断回问链表

原题描述:

请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

1.判断回文链表-双指针

var isPalindrome = function(head) {
    var arr = [];
    var start = head;
    // 转成数组
    while (start) {
        arr.push(start.val);
        start = start.next;
    }
    // 一位数字的回文数,这个要注意
    if (arr.length === 1) {
        return true;
    }
    // 双指针
    for (var i = 0,
    j = arr.length - 1; i < j; i++, j--) {
        if (arr[i] !== arr[j]) {
            return false;
        }
    }
    return true;
};

2.判断回文链表-出栈

var isPalindrome = function(head) {
    var arr = [];
    var start = head;
    // 转成数组
    while (start) {
        arr.push(start.val);
        start = start.next;
    }
    // 一位数字的回文数,这个要注意
    if (arr.length === 1) {
        return true;
    }
    var end = head;
    while(end) {
      if(end.val !== arr[arr.length-1]) {
          return false;
      }
      arr.pop(); // 把数组当成一个栈
      end = end.next;
    }

以上两种都是 O(n) 时间复杂度

3.判断回文链表-快慢指针

利用快慢指针的特性先找出中间值,快指针走两步,慢指针走一步,当快指针走完链表时,慢指针正好走到链表的一半。

  1. 需要一个链表的副本
  2. 需要对链表进行反转,以便可以反向指针

链表反转方法

var reverseList = function(head) {
    if(head == null || head.next == null){
			return head;
		}
        let res = reverseList(head.next);
        head.next.next = head;
		head.next = null;
        return res;
};

用到了递归方法,更好的理解什么是递归

  • 递:按顺序建立联系
  • 归:归是得出结果的过程
var isPalindrome = function(head) {
    if (!head) {
        return true;
    }
    var fast = head;
    var slow = head;

    while (fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    var rev = reverseList(slow);
    while (rev !== null && head !== null) {
        if (head.val !== rev.val) {
            return false;
        }
        rev = rev.next;
        head = head.next;
    }
    return true;
};

O(0) 时间复杂度

其他

关于链表相关的问题

  1. 如何判断链表是否存在环?
  2. 如何知道环的长度?
  3. 如何找出环的连接点在哪里?
  4. 带环链表的长度?