力扣labuladong一刷day15天K個一組翻轉鏈表與回文鏈表

一、25. K 個一組翻轉鏈表

題目鏈接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
思路：k個一組翻轉鏈表，每k個翻轉抽取出一個單獨的方法reverse，翻轉a到b，返回的結果是新的頭結點。
然后遞歸調用reverseKGroup，每次返回的都是新的頭結點，新的頭結點要接在上一個尾結點的位置也就是未翻轉前的head即a。

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 a;b = b.next;}ListNode newHead = reverse(a, b);a.next = reverseKGroup(b, k);return newHead;}ListNode reverse(ListNode a, ListNode b) {ListNode pre = null, cur = a, nex = b;while (cur != b) {nex = cur.next;cur.next = pre;pre = cur;cur = nex;}return pre;}
}

二、234. 回文鏈表

題目鏈接：https://leetcode.cn/problems/palindrome-linked-list/
思路：類比于字符串，如果是判斷是否是回文，只需要從兩端向中間進行逐個比較，如果是尋找回文子串則要考慮奇數偶數從中間向兩端尋找。

這里是判斷鏈表是否是回文鏈表。只需要用一個全局變量記錄head值，然后遞歸后序遍歷，逐個比較。

ListNode left = null;public boolean isPalindrome(ListNode head) {left = head;return reverse(head);}boolean reverse(ListNode right) {if (right == null) return true;boolean res = reverse(right.next);res = res && left.val == right.val;left = left.next;return res;}

但這樣其實是多比較了一半，也可以先試用快慢指針找到中點，然后翻轉后一半，再來逐個比較，只要右邊短的停止了就停止。

class Solution {public boolean isPalindrome(ListNode head) {ListNode slow = head, fast = head, left = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}if (fast != null) slow = slow.next;slow = reverse(slow);while (slow != null) {if (left.val != slow.val) return false;left = left.next;slow = slow.next;}return true;}ListNode reverse(ListNode node) {ListNode pre = null, cur = node, nex = node;while (cur != null) {nex = cur.next;cur.next = pre;pre = cur;cur = nex;}return pre;}
}