链表高频题目和必备技巧

题目一：返回两个无环链表相交的第一个节点

算法思路：首先，如果两个无环链表相交，那么从相交节点开始，两个链表就合为了同一个链表，因此它们的最后一个节点一定是同一个；反之，如果两个链表的最后节点不是同一个，那么这两个链表一定不相交。

单链表只有一个next指针，不可能出现上述情况

然后，在两个链表相交的情况下，我们得到两个链表长度的差值differ，让长链表的头结点先后移differ个长度，然后同时遍历两个链表，即可找到他们相交的第一个节点。

代码实现

    public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {
        if (h1 == null || h2 == null) {
            return null;
        }
        ListNode a = h1, b = h2;
        int diff = 0;  // 两链表长度的差值 
        while (a.next != null) {
            a = a.next;
            diff++;
        }
        while (b.next != null) {
            b = b.next;
            diff--;
        }
        // 如果两个链表的尾节点不相同，说明不相交
        if (a != b) {
            return null;
        }
        // a指向长链表的头结点，b指向短链表的头结点
        if (diff >= 0) {
            a = h1;
            b = h2;
        } else {
            a = h2;
            b = h1;
        }
        diff = Math.abs(diff);
        // 长链表的头结点先后移diff个长度
        while (diff-- != 0) {
            a = a.next;
        }
        // 遍历两个链表
        while (a != b) {
            a = a.next;
            b = b.next;
        }
        return a;
    }

题目二：每k个节点一组翻转链表

题目描述

首先，链表的题目，在不要求空间的情况下，都可以采用容器的思想，比如本题，可用数组来存储链表的节点内容，在数组中进行每k个节点的翻转，因为数组可通过下标定位节点，因此翻转更加方便。

而不使用额外空间的话，就只能对原链表进行操作。我们每k个节点为一组划分，首先需要记录第一组的最后一个节点，因为这是我们最后要返回结果的头结点，然后该组节点翻转，翻转之后的尾结点先指向下一组的头，之后对下一组节点进行翻转，翻转之后，我们要让上一组的尾结点指向该组翻转后的头节点，重复上述操作。

图示过程

代码实现

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = teamEnd(start, k);
        if (end == null) {
            return head;
        }
        // 第一组很特殊因为牵扯到换头的问题
        head = end;
        reverse(start, end);
        // 翻转之后start变成了上一组的结尾节点
        ListNode lastTeamEnd = start;
        while (lastTeamEnd.next != null) {
            start = lastTeamEnd.next;
            end = teamEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            lastTeamEnd.next = end;
            lastTeamEnd = start;
        }
        return head;
    }

    // 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
    public static ListNode teamEnd(ListNode s, int k) {
        while (--k != 0 && s != null) {
            s = s.next;
        }
        return s;
    }

    // s -> a -> b -> c -> e -> 下一组的开始节点
    // 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
    public static void reverse(ListNode s, ListNode e) {
        e = e.next;
        ListNode pre = null, cur = s, next = null;
        while (cur != e) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        s.next = e;
    }

题目三：复制带随机指针的链表

题目描述

本题设置的链表节点的结构定义为

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

比单链表的节点多了一个随机指针，可能指向链表中的任何一个节点（包括自己），也可能指向空，需要复制该链表。

我们同样可以使用容器的思想，使用hash表，key对应原本链表节点，value对应拷贝后的链表节点。初始时，我们通过next指针遍历链表，建立好原本链表节点与拷贝后链表节点的对应关系，然后处理节点之间的关联关系。我们通过key对应节点的next指针，找到下一个结点，再通过这个节点在hash表中的对应关系，找到其对应的value节点，然后让key对应的value节点的next指向该节点，这样就建立了拷贝节点间的next关系。同理，我们也可以通过key对应节点的random指针找到拷贝节点的random指针应该对应的关系。

通过hashmap实现

如果不使用额外空间的话，我们可以先将拷贝节点创建后放在原节点之后

再每两个节点（即一个原本链表节点和一个拷贝链表节点）为一组，先通过原本节点的random指针找到下一个其指向的随机节点，然后该随机节点的下一个就对应着拷贝节点，因此可以让该组中拷贝节点的random指向它，然后再处理后两个节点。

处理完整个链表后，原本链表和拷贝链表的random指针是正确的，唯有next指针是交错的，因此最后只需调整next指针，让两个链表分开即可。

    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // 1 -> 2 -> 3 -> ...
        // 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node copy = null;
        // 利用上面新老节点的结构关系，设置每一个新节点的random指针
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            copy.random = cur.random != null ? cur.random.next : null;
            cur = next;
        }
        Node ans = head.next;
        cur = head;
        // 新老链表分离 : 老链表重新连在一起，新链表重新连在一起
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }
        // 返回新链表的头节点
        return ans;
    }

题目四：判断是否为回文链表，即整个链表是一个关于中轴对称的结构

首先，回文链表的结构如下

回文链表结构

如果通过容器实现，我们可以借助栈，先将链表所有结点入栈，然后依次出栈，如果出栈结果与原来链表结构一致，说明是回文链表

用栈判断回文结构

如果不使用额外空间的话，就需要用到一个链表中的常用技巧——快慢指针。设置一个慢指针，每次一个节点来遍历链表，同时设置一个快指针，每次两个节点来遍历链表，当快指针无法再后移时，此时慢指针所指节点就是链表的中点，我们将中点之后的链表反转，然后从头和尾遍历链表，如果结果都一样，说明就是回文结构。

奇数个节点的情况

偶数个节点的情况

最后还要注意，需要将链表还原成原本的结构。

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        // 找中点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 现在中点就是slow，从中点开始往后的节点逆序
        ListNode pre = slow;
        ListNode cur = pre.next;
        ListNode next = null;
        pre.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 上面的过程已经把链表调整成从左右两侧往中间指
        // head -> ... -> slow <- ... <- pre
        boolean ans = true;
        ListNode left = head;
        ListNode right = pre;
        // left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false
        while (left != null && right != null) {
            if (left.val != right.val) {
                ans = false;
                break;
            }
            left = left.next;
            right = right.next;
        }
        // 本着不坑的原则，把链表调整回原来的样子再返回判断结果
        cur = pre.next;
        pre.next = null;
        next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return ans;
    }

2019年408考研的数据结构的算法题就用到了类似的做法

2019年408真题第41题

本题其实就是回文链表中，将左右都指向中点后，再次遍历时，将首尾节点在遍历过程中串联起来即可。

题目五：链表的第一个入环节点

题目描述

如果使用容器的方法，我们可以使用hashset，每次将节点加入hashset中，如果该节点在hashset中已存在，那么其就是入环的第一个节点。

不使用额外空间的方法，我们定义快慢两个指针，快指针一次后移两个单位，慢指针一次后移一个单位，如果快指针指向了null，说明无环，否则，快慢指针一定会相遇，此时，慢指针保持不动，快指针回到头结点，一次后移一个单位，最终，两指针一定会相交于入环的第一个节点。

快慢指针

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

题目六：链表排序

我们知道对于数组排序，时间复杂度最好是O（n*logn），但往往空间复杂度无法达到常数级，但在链表中可以实现。比如归并排序运用于链表中时，可以不使用额外空间，在将数组二分之后，进行比较排序时，链表可直接修改next指针实现，不需要额外空间。同时如果使用非递归实现归并排序，可以做到真正常数级空间复杂度。

    public static ListNode sortList(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        // l1...r1 每组的左部分
        // l2...r2 每组的右部分
        // next 下一组的开头
        // lastTeamEnd 上一组的结尾
        ListNode l1, r1, l2, r2, next, lastTeamEnd;
        for (int step = 1; step < n; step <<= 1) {
            // 第一组很特殊，因为要决定整个链表的头，所以单独处理
            l1 = head;
            r1 = findEnd(l1, step);
            l2 = r1.next;
            r2 = findEnd(l2, step);
            next = r2.next;
            r1.next = null;
            r2.next = null;
            merge(l1, r1, l2, r2);
            head = start;
            lastTeamEnd = end;
            while (next != null) {
                l1 = next;
                r1 = findEnd(l1, step);
                l2 = r1.next;
                if (l2 == null) {
                    lastTeamEnd.next = l1;
                    break;
                }
                r2 = findEnd(l2, step);
                next = r2.next;
                r1.next = null;
                r2.next = null;
                merge(l1, r1, l2, r2);
                lastTeamEnd.next = start;
                lastTeamEnd = end;
            }
        }
        return head;
    }

    // 包括s在内，往下数k个节点返回
    // 如果不够，返回最后一个数到的非空节点
    public static ListNode findEnd(ListNode s, int k) {
        while (s.next != null && --k != 0) {
            s = s.next;
        }
        return s;
    }

    public static ListNode start;

    public static ListNode end;

    // l1...r1 -> null : 有序的左部分
    // l2...r2 -> null : 有序的右部分
    // 整体merge在一起，保证有序
    // 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
    public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
        ListNode pre;
        if (l1.val <= l2.val) {
            start = l1;
            pre = l1;
            l1 = l1.next;
        } else {
            start = l2;
            pre = l2;
            l2 = l2.next;
        }
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                pre = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) {
            pre.next = l1;
            end = r1;
        } else {
            pre.next = l2;
            end = r2;
        }
    }