链表-EmiyaCC 摘录室

链表反转
- 递归的链表翻转
- 迭代的链表翻转
K 个一组翻转链表
回文链表

链表反转

对于链表的反转，一般有两种方法，递归和迭代，递归比较难以理解，并且效率没有迭代的高，但是写着帅，可以装 X。

递归的链表翻转

第一步，整个翻转：

class Solution {
    public ListNode reverseList(ListNode head) {
        // 只聚焦第一次递归，定义本函数内的空间为本次元，递归中的空间为其他次元
        // base case，这里返回的本次元的最后一个节点（翻转之后会变成头节点）
        if (head == null || head.next == null) return head;
        // 递归返回的节点，在其他次元已经变成了头节点，但是在本次元还是尾节点，所以用 last 表示
        ListNode last = reverseList(head.next);
        // 此刻在其他次元 head 后面的已经完成了翻转，但是在本次元还没有翻转，所以在此时需要进行拼接，翻转后这个次元的 head.next 在上代码的次元是最后一个，故要在 head.next 后面接上本结点 head
        head.next.next = head;
        // 同理，翻转之后 head 的后面应该是空
        head.next = null;
        // 返回翻转后的头节点
        return last;
    }
}

第二步（1），翻转前 n 个节点：

class Solution {
    // 对比全部翻转，翻转前 n 个节点，需要记录下 n + 1 个节点，好方便拼接，所以这里需要定义一个 next 记录
    ListNode next;

    ListNode reverseN(ListNode head, int n) {
        // base case，对比全部翻转，翻转前 n 个节点的停止条件变成 n == 1，同时记录下下一个节点
        if (n == 1) {
            next = head.next;
            return head;
        }
        // 递归时，注意 n - 1，因为少了本次元的节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 对比全部翻转，这里要注意的是，翻转之后 head 的后面应该是 next
        head.next = next;
        return last;
    }
}

第二步（2），翻转到某一节点：

class Solution {
    ListNode next;

    ListNode reverseN(ListNode head, ListNode tail) {
        if (head == tail) {
            next = head.next;
            return head;   
        }
        ListNode last = reverseN(head.next, tail);
        head.next.next = head;
        head.next = next;
        return last;
    }
}

第三步，翻转一个区间：

// 先写出翻转前 n 个节点，再推进到可以翻转的点那，把翻转一个区间转变成翻转前 n 个节点
class Solution {
    ListNode next;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // left == 1，对应翻转前 n 个节点问题，此时返回的是翻转后的头节点
        if (left == 1) {
            return reverseN(head, right);
        }
        // left 不等于 1 时，则往后递归，同时处理好顺序关系，让 head 后面接递归后的结果（也就是翻转好的返回值，即下一次元的头节点）
        head.next = reverseBetween(head.next, left - 1, right - 1);
        // 返回值是本次元的头节点
        return head;
    }

    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            next = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = next;
        return last;
    }
}

迭代的链表翻转

第一步，整个翻转：

class Solution {
    public ListNode reverseList(ListNode head) {
        // 对于链表，虚拟头节点可以使头节点变成非头节点，减少了逻辑判断，很棒
        ListNode dummy = new ListNode(0);
        // 对于不同的题，dummy 后面接的会有不同，是接 null 还是 head，需考虑题意
        dummy.next = null;
        ListNode next = null;
        // 头插法，翻转整个链表
        while (head != null) {
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }
}

第二步（1），翻转前 n 个节点：

class Solution {
    public ListNode reverseN(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = null;
        // 对比翻转全部，此处添加计数器 count
        int count = 0;
        // 对比翻转全部，此处添加记录头节点的引用 last，因为翻转后本次元的头节点会变成翻转部分的尾节点，为之后的拼接做准备
        ListNode last = head;
        ListNode next = null;
        // 对比翻转全部，此处终止条件修改成 count < n
        while (count < n) {
            count ++;
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        // 最后拼接整个链接
        last.next = next;
        return dummy.next;
    }
}

第二步（2），翻转到某一结点：

class Solution {
    public ListNode reverseList(ListNode head, ListNode tail) {
        // 对于链表，虚拟头节点可以使头节点变成非头节点，减少了逻辑判断，很棒
        ListNode dummy = new ListNode(0);
        // 对于不同的题，dummy 后面接的会有不同，是接 null 还是 head，需考虑题意
        dummy.next = null;
        // 记录下头节点
        ListNode last = head;
        ListNode next = null;
        // 头插法，翻转整个链表
        while (head != tail) {
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        last.next = next;
        return dummy.next;
    }
}

第三步，翻转一个区间：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 本题 dummy 后面接的是 head
        ListNode dummy = new ListNode(0, head);
        // 要记录前一节点，所以多一个 prev
        ListNode prev = dummy;
        // 找到可以进行翻转前 n 个节点的那个节点，并记录该节点的前一节点
        while (left > 1) {
            left --;
            right --;
            head = head.next;
            prev = prev.next;
        }
        // 拼接链表
        prev.next = reverseN(head, right);
        return dummy.next;
    }

    public ListNode reverseN(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = null;
        int count = 0
        ListNode last = head;
        ListNode next = null;
        while (count < n) {
            count ++;
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        last.next = next;
        return dummy.next;
    }
}

反转链表

反转链表 II

K 个一组翻转链表

本题算是翻转一个区间的进阶版本，大概就是两个部分，第一部分是翻转前 n 个节点（或者翻转到某一结点），第二部分是主函数，可以是递归（类似翻转一个区间），也可以是迭代，下面用迭代完成代码（跟乐高一样，可以拼接）

// https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution {    
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode tail = head;
        while (head != null) {
            for (int i = 0; i < k; i ++) {
                if (tail == null) {
                    return dummy.next;
                }
                tail = tail.next;
            }
            prev.next = reverseN(head, tail);
            prev = head;
            head = tail;
        }
        return dummy.next;
    }

    ListNode reverseN(ListNode head, ListNode tail) {
        ListNode dummy = new ListNode(0);
        dummy.next = null;
        ListNode last = head;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        last.next = next;
        return dummy.next;
    }
}

回文链表

// (https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution {
    ListNode left;

    public 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;
    }
}

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) {
            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 tail) {
        ListNode dummy = new ListNode(0);
        dummy.next = null;
        ListNode next = null;
        while (head != tail) {
            next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;
        }
        return dummy.next;
    }
}

Reference：

https://labuladong.gitee.io/algo/

https://leetcode-cn.com/problems/