每日算法 回文链表

例题：234. 回文链表

题目描述：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

代码：

//快慢指针版本（翻转后半段链表）
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null){    //fast != null即链表为奇数个节点，slow要往后走一个节点才能到中点
               slow = slow.next;
        }
        
        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 pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
//例如输入：head = [1,2,3,2,1] 其结果链表为 [1 → 2 → 3 → 2 ← 1]
//这个方法相比于力扣下面的方法去掉了他们的劣势部分，是一个优化的版本。重要的是这个方法没断链。（虽然慢了一点）

力扣官方题解：

//迭代版
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}
//通过遍历链将所有的值按链的顺序存储下来，并通过普通的双指针将List中的值一个从前往后，一个从后往前遍历并进行值的相等比较，来判断是否是回文。

//常规递归版
class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {    
                //递归到最后一个节点的next为null，所以返回true
                //那么这个if判断条件内反向就是false，即跳过判断
                return false;
            }
            if (currentNode.val != frontPointer.val) {    
                //进行前后半段节点回文判断，前半段往后递进，后半段往前递进
                //前后半段相互比较是否相等，相等则接着往下判断，不相等则不是回文返回false
                return false;
            }
            //因为递归导致后半段自动往前递进，而前半段需要手动向后递进
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}
/*
例如：输入head = [1,2,3,2,1]

调用 recursivelyCheck(head) 方法，开始递归检查链表是否为回文。

在 recursivelyCheck(ListNode currentNode) 方法中，首先传入的 currentNode 是链表的头节点 head。

当 currentNode 不为 null 时，先递归地调用 recursivelyCheck(currentNode.next)，即使用递归的方法到达链表的最后一个节点。

当 currentNode 为最后一个节点时，递归返回，开始执行 if (currentNode.val != frontPointer.val) 的判断。由于此时 currentNode.val 为 1，而 frontPointer.val 也为 1，因此条件成立，继续执行 frontPointer = frontPointer.next;，即将 frontPointer 向后移动一位，指向第二个节点。
回到上一层递归，继续执行 if (!recursivelyCheck(currentNode.next)) 的判断。由于此时 currentNode 是倒数第二个节点，所以进入下一层递归，直到最后一个节点。然后开始比较倒数第二个节点的值 2 与 frontPointer 指向的节点的值 2 是否相等。

以此类推，继续比较链表的节点值。

最后，当链表的所有节点都比较完毕时，recursivelyCheck 方法返回 true，表明链表是回文的。
*/

//这个递归的方法我们其实会发现有一点问题，那就是这个方法递归会做一些重复的回文判断。因为这个递归是直接从尾→头进行回溯，这就导致了其实实际上并没有前后半段之分，而是正逆向遍历链表来互相挨个进行节点的相等比较，这就会导致做多了一次已经判断过的回文判断，做了一次多余的工作。

//所以会造成递归甚至比常规双指针迭代要慢了很多（这道题常规迭代8ms，这个递归16ms）

//快慢指针版本
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

//这个相比于前面第一种（非官方那个），还要还原链表并返回结果，多做了一些而外的工作，所以相比于不用还原链表的方法慢了一点。

//快慢指针（前半段链表翻转）
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head, pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            // 反转前半部分的链表，变成两个链表
            ListNode next = slow.next;
            slow.next = pre;
            pre = slow;
            slow = next;
        }
        // 节点数为奇数时，特殊处理下
        if (fast != null)
            slow = slow.next;
        // 对比两个链表的值是否完全相同
        while (slow != null) {
            if (slow.val != pre.val)
                return false;
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }
}
//简化版
/*
    例如输入：head = [1,2,3,2,1]
    初始状态：
        head -> 1 -> 2 -> 3 -> 2 -> 1 -> null
        fast = head
        slow = head
        pre = null
            
    第一次循环：
        ListNode next = slow.next;
        slow.next = pre;
        pre = slow;
        slow = next;
        
        fast = fast.next.next = 3
        next = slow.next = 2
        slow.next = pre = null
        pre = slow = 1
        slow = next = 2
        
null <- 1    2 -> 3 -> 2 -> 1 -> null
        ^    ^    ^
        |    |    |
       pre slow fast
    
    第二次循环：
        fast = fast.next.next = 1 (到达链表末尾)
        next = slow.next = 3
        slow.next = pre = 1 (slow = 2，所以这里就变成了 null←1←2 )
        pre = slow = 2
        slow = next = 3
        
null <- 1 <- 2    3 -> 2 -> 1 -> null
             ^    ^            ^
             |    |            |
            pre  slow       fast
    
    之后便因为while条件不足结束循环，执行下面的代码。
*/

//这个方法和第一种相比关键就在于第一种方法是快慢指针之后再进行的翻转，这个是在快慢指针的时候就已经进行了翻转，而且这个方法断链了，将一条链表拆成了两条。