LeetCode学习计划：LeetCode 75-Level-2

19. 删除链表的倒数第 N 个结点

问题描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

解题思路

双指针直接开冲！
一个指针先跑n个结点，如果它跑到了null，说明要删除的是头结点，直接返回头结点的下一个结点即可；如果没有跑到null，让两个指针一起跑直到指针1的下个结点为null，此时删除指针2的下个结点即可。

代码示例（JAVA）

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node1 = head, node2 = head;
        for (int i = n; i > 0; i--) {
            node1 = node1.next;
        }
        if (node1 == null) {
            return head.next;
        }
        while (node1.next != null) {
            node1 = node1.next;
            node2 = node2.next;
        }
        node2.next = node2.next.next;
        return head;
    }
}

234. 回文链表

问题描述

给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

示例

解题思路

1. 遍历链表组成字符串并与翻转后的字符串比较
2. 快慢指针找到中间位置（两个指针一起出发，一个步长为1，一个步长为2），并将后一部分的节点进行翻转，翻转后从两端进行比较。（为了将空间复杂度减少到O(1)）

代码示例（JAVA）

1. 遍历链表组成字符串并与翻转后的字符串比较

class Solution {
    public boolean isPalindrome(ListNode head) {
        StringBuilder str1 = new StringBuilder();
        ListNode node = head;
        while (node != null) {
            str1.append(node.val);
            node = node.next;
        }
        return str1.toString().equals(str1.reverse().toString());
    }
}

2. 快慢指针、翻转链表

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null && head.next == null) {
            return true;
        }
        // 快慢指针找到中间位置
        ListNode first = head, second = head;
        while (second.next != null && second.next.next != null) {
            first = first.next;
            second = second.next.next;
        }
        ListNode mid = first;
        ListNode afterHalfHead = mid.next;
        // 将后面部分的链表进行翻转
        ListNode newHead = null;
        ListNode cur = afterHalfHead;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        // 从两边进行比较
        while (head != newHead && newHead != null) {
            if (head.val != newHead.val) {
                return false;
            }
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
}