Singly linked list（单链表）- 4

2021-07-27

1. 回文串

Reference: 如何判断回文链表 - labuladong的算法小抄 (gitbook.io)

目标

搞懂回文串（Palindrome）是什么（从前向后读和从后向前读一样的字符串）
搞懂寻找回文串和判断回文串的核心思想
知道如何在单链表结构中判断回文串
优化单链表回文串判定的空间复杂度

2. 如何判断一个「单链表」是不是回文

思路 1 - 反转链表

由于单链表无法从后往前遍历，所以无法使用双指针。

那么如何比较呢？我们之前学了反转单链表的算法，现在我们可以结合反转来创造一条新的单链表。

这样一来，我们就拥有了一正一反两条单链表，只要比较两者是否相同即可。

思路 2 - 二叉树后序遍历

由于链表具有递归结构，所以树结构其实是链表的衍生产物。

链表可以做前序遍历和后序遍历。

/**
 * 单链表节点的定义：
 * public class ListNode {
 *     int val;
 *     ListNode next;
 * }
 */

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

后序遍历的时候，就把代码写在 traverse 的后面，实现从后往前打印。

/* 后序打印单链表中的元素值 */
void traverse(ListNode head) {
    if (head == null) return;
    traverse(head.next);
    // 后序遍历代码
    print(head.val);
}

思路二代码

// 左侧指针
ListNode left;

boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}

boolean traverse(ListNode right) {
    if (right == null) return true;
    boolean res = traverse(right.next);
    // 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
    return res;
}

这么做的核心逻辑是什么呢？实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。

复杂度比较

无论造一条反转链表还是利用后序遍历，算法的时间和空间复杂度都是 O(N)。

3. 优化空间复杂度

双指针技巧

1. 慢指针找到中点

先用双指针技巧中的快慢指针来找到链表的中点。

两个指针一开始都定位在 head
慢指针每次走一步，快指针每次走两步
结束 while 的条件是快指针.next = null 或者快指针=null
- 所以快指针就算走两步也最多是 null，不会变成 null.next 这种情况
因为快指针走的速度比慢指针快一倍，所以当快指针走到终点的时候，慢指针正好在中间！

ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 指针现在指向链表中点

2. 奇偶数

假如链表的 node 个数是奇数，1->2->3->4->5，当快指针走到 5 的时候，慢指针在 3；
假如链表的 node 个数是偶数，1->2->3->4，当快指针走到 null 的时候，慢指针在 3；

在奇数的情况下，慢指针需要再向前一步（为啥？）

1->2->3->4->5，慢指针在 4

if (fast != null)
    slow = slow.next;

3. 反转链表

从慢指针的位置开始进行链表反转，反转之后得到 1->2->3->5->4

然后开始比较，左node = head = 1，右node = 5

当右node不为空的时候，假如左node value 和右node value相同，那么我们继续向前移动两个node；

否则返回 false。

也就是说，假设 1->2->3->2->1，反转之后是1->2->3->1->2，比较之后发现1->2重复，继续向前时right=null（因为是奇数），但这个链表还是满足回文链表的要求，所以返回true。

ListNode left = head;
ListNode right = reverse(slow);

while (right != null) {
    if (left.val != right.val)
        return false;
    left = left.next;
    right = right.next;
}
return true;

// 迭代法进行链表反转
ListNode reverse(ListNode head) {
    ListNode previous = null, current = head;
    while (current != null) { // previous = last node
        ListNode next = current.next; 
        current.next = previous; // 反转
        previous = current; // 向前移动
        current = next;
    }
    return previous; // previous = new head
}

如何避免破坏链表的原始结构

我们只需要知道比较结束之后左右 node 的位置，再进行一次翻转就可以了。

left.next = reverse(right);

复杂度

这种双指针法的时间复杂度 O(N)，空间复杂度 O(1)。

完整版代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode left = head;
        // find the middle node and reverse
        ListNode right = reverse(findMiddle(head));
        // compare left with the reversed middle node
        while (right != null && left != null){
            if (right.val != left.val)
                return false;
            right = right.next;
            left = left.next;
        }
        return true;
    }

    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null)
            slow = slow.next;
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

4. 结语

「寻找」回文串的思路是从中间向两边扩展；「判断」回文串的思路是从两边向中间收缩。

但是由于单链表无法从后往前遍历，我们可以采取以下几个方法：

自己造一条反转链表，然后进行比较；
利用链表的递归属性进行后序遍历，也就是用递归函数的堆栈来处理；

如何提高效率？判断回文串的时候，我们可以只反转一部分链表，这样可以把空间复杂度降到 O(1)。

PS: 参考的原文中有一些动画图可以帮助理解~

Luna Tech