反转链表和判断回文链表

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：
递归方法：
我们只需要考虑某个结点的递归行为即可。
当结点为空时或者结点的下一个结点为空，直接返回当前结点。
当结点不为空时，reverseList(head.next)可以得到后面已经反转好的链表。我们只需要让head.next.next指向head，再让head指向空即可。

public ListNode reverseList(ListNode head) {

    if (head == null || head.next == null) {
        return head;
    }

    ListNode res = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return res; 
}

迭代方法：
我们需要用到三个指针，一个pre指向当前结点的前一个结点，一个cur记录当前节点，一个post记录当前节点的下一个结点。

每一次迭代，都让cur的下一个指针指向pre，再整体前移一格。
cur.next = pre;
pre = cur;
cur = post;

public ListNode reverseList(ListNode head) {

    ListNode cur = head, pre = null;

    while (cur != null) {
        ListNode post = cur.next;
        cur.next = pre;
        pre = cur;
        cur = post;
    }

    return pre;
}

92.反转链表Ⅱ

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

解题思路：
我们可以把链表整体拆分成三段，第一段是[0,left), 第二段是[left,right]，第三段是（right，末尾）。分别用三个指针记录这三段链表，将中间那段用上述方法反转，再将他们进行整合即可。为了避免头节点的不同情况，我们需要定义一个空节点作为新的头节点。

public ListNode reverseBetween(ListNode head, int left, int right) {

    ListNode dummyHead = new ListNode();
    dummyHead.next = head;

    ListNode pre = dummyHead;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    ListNode rightNode = pre;
    for (int i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }

    ListNode leftNode = pre.next;
    ListNode curr = rightNode.next;

    pre.next = null;
    rightNode.next = null;

    reverseList(leftNode);

    pre.next = rightNode;
    leftNode.next = curr;

    return dummyHead.next;
}

public void reverseList(ListNode head) {

    ListNode cur = head, pre = null;

    while (cur != null) {
        ListNode post = cur.next;
        cur.next = pre;
        pre = cur;
        cur = post;
    }

}

25.K个一组反转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解题思路：

我们先构建一个区间反转链表方法，reverse(ListNode a, ListNode b)，该方法为反转a到b之间的节点;

这题我们采用递归思路来解决，我们站在某个节点head位置来看,

首先，当head为空时，我们直接返回null；

我们每次需要将k个节点进行反转，所以我们需要找到这一段区间 [a, b) 的链表头尾节点。

我们用a来记录头节点，b来记录尾节点的下一个节点。

a 就是 head，b就需要使用循环前进k步。

注意，当如果节点总数不是 k 的整数倍，那么直接返回head即可。

用newHead记录区间链表反转后的结果。

ListNode reverseKGroup(ListNode head, int k) //就代表完成以head为头，K个一组反转链表，并返回头节点

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        
        if (head == null) return null;

        ListNode a = head, b = head;

        for (int i = 0; i < k; i++) {
            if (b == null) return head;
            b = b.next;
        }
        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);

        return newHead;
    }

    public ListNode reverse(ListNode a, ListNode b) {

        ListNode pre = null;
        ListNode cur = a;

        while (cur != b) {
            ListNode post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }

        return pre;
    }
}

234.回文链表

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

解题思路：

我们使用快慢指针找到链表中点，将链表分为前半段和后半段。将后半段链表反转后，逐一对比。

需要对链表长度分情况讨论

当链表长度为奇数时，fast != null, slow.next为后半段头节点。

当链表长度为偶数时，fast ==null, slow为后半段头节点

class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = (fast == null) ? slow : slow.next;

        ListNode right = reverseList(slow);
        ListNode cur = head;
        while (right != null) {

            if (cur.val != right.val) {
                return false;
            }
            cur = cur.next;
            right = right.next;
        }

        return true;
    }

    public ListNode reverseList(ListNode head) {

        ListNode cur = head, pre = null;

        while (cur != null) {
            ListNode post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }

        return pre;
    }
}

​