234.Palindrome Linked List(回文链表)


题目:判断一个链表是否回文。

题目链接

一.单向链表

Recall

  • 单向链表是一种线性的数据结构。
  • 包含数据体data和指向下一个节点的指针link。
  • 第一个节点称为head,最后一个节点指向null。
  • 单向链表是分散存储的。

Notes

  • 什么是单向链表(singly linked list)?

    1单向链表是一种线性的数据结构,但是其元素的存储并不是连续的,而是通过指针(pointer)来指向下一个元素。

    2单向链表的每一个元素我们称之为node,每一个node包含两个字段:data(用于存储数据),link(指针来指向下一个元素)。

    3单向链表的第一个node,我们称之为头(head/front),最后一个node的link指向一个null。如图:

  • 单向链表和数组的区别?

    数组的缺点:

    1数组的长度是固定的

    2在数组中插入/删除的成本非常高。对于一个有序的数组,如果我们要在中间插入,那么我们必需删掉后面的所有节点然后结合新的节点全部重新插入。删除也类似。

    单向链表的优势:

    1单向链表的长度是动态的。

    2插入和删除成本很低。

    单向链表的缺点:

    1无法进行随机访问。我们要访问其中的一个节点,必须要从第一个节点开始遍历。

    2需要额外的内存开销来维护链表间的指针。内存消耗比数组大。

    3node的存储是不连续的,因此访问元素的时间会大幅度增加,另外这不利于cpu缓存。

    4单向链表的逆向遍历比较困难,双向链表可以更好的实现逆向遍历,但是却又增加了逆向指针的内存开销。

    SUMMARY:单向链表是一种简单的线性数据结构。

二.递归:

递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。

循环:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门(若前面两扇门都一样,那么这扇门和前两扇门也一样;如果第二扇门比第一扇门小,那么这扇门也比第二扇门小,你继续打开这扇门,一直这样继续下去直到打开所有的门。但是,入口处的人始终等不到你回去告诉他答案。

1、定义 (什么是递归?)

在数学与计算机科学中,递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上,递归,顾名思义,其包含了两个意思: 和 ,这正是递归思想的精华所在。

2、递归思想的内涵(递归的精髓是什么?)

正如上面所描述的场景,递归就是有去(递去)有回(归来),如下图所示。“有去”是指:递归问题必须可以分解为若干个规模较小,与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决,就像上面例子中的钥匙可以打开后面所有门上的锁一样;“有回”是指 : 这些问题的演化过程是一个从大到小,由近及远的过程,并且会有一个明确的终点(临界点),一旦到达了这个临界点,就不用再往更小、更远的地方走下去。最后,从这个临界点开始,原路返回到原点,原问题解决。

3、递归的三要素

  • 明确递归终止条件;
  • 给出递归终止时的处理办法;
  • 提取重复的逻辑,缩小问题规模

4、递归算法的编程模型

在我们明确递归算法设计三要素后,接下来就需要着手开始编写具体的算法了。在编写算法时,不失一般性,我们给出两种典型的递归算法设计模型,如下所示。

模型一:在递去的过程中解决问题

function recursion(大规模){
    if (end_condition){      // 明确的递归终止条件
        end;   // 简单情景
    }else{            // 在将问题转换为子问题的每一步,解决该步中剩余部分的问题
        solve;                // 递去
        recursion(小规模);     // 递到最深处后,不断地归来
    }
}

模型二: 在归来的过程中解决问题

function recursion(大规模){
    if (end_condition){      // 明确的递归终止条件
        end;   // 简单情景
    }else{            // 先将问题全部描述展开,再由尽头“返回”依次解决每步中剩余部分的问题
        recursion(小规模);     // 递去
        solve;                // 归来
    }
}

三.思路:

常规思路是逆序这个链表,然后对比逆序后的表和原表是否回文。

逆序的方法有三种。1是通过压栈来逆序。2是通过迭代逆序。3是通过递归逆序。

效率最好的是迭代。

最简单实现的是压栈。

最简洁的是递归。

四.优化:

先找到链表的中间节点,然后逆序中间节点。再用head和中间节点逆序后对比出结果。

五.理解:

对我来说画图是更容易理解的。

核心代码只有两行。

六.代码:

迭代的实现:

ListNode reverseLL(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        ListNode reverseNode = null;
        ListNode splitNode = head;
        while (null != splitNode) {
            ListNode temp = splitNode.next;
            splitNode.next = reverseNode;
            reverseNode = splitNode;
            splitNode = temp;
        }
        return reverseNode;
    }

递归的实现:

public ListNode recursion(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        ListNode last = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

参考:

对于递归有没有什么好的理解方法?

Linked list - Wikipedia

Single Linked List

Linked List | Set 1 (Introduction) - GeeksforGeeks

声明:Eironn's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 234.Palindrome Linked List(回文链表)


Java开发,同时会一些旁门左道。