25-算法面试专题-链表.md

```java
package com.xiaodai.algorithm;

/**
 * Author ：dai
 * Date   ：2020/12/25 5:04 下午
 * Description：
 */
public class LinkedListUtil {


    /**
     * 链表的节点，可实现成泛型
     */
    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    /**
     * 双向列表的节点结构，可实现成泛型
     */
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }


    /**
     * 1、检测链表是否成环。返回成环是否，第一次相遇并不保证是成环的节点
     *
     * @param head
     * @return
     */
    public boolean hasCycle(Node head) {

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

        Node slow = head;
        Node fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        // 有环的话一定追的上，但不一定是第一次成环的节点
        return true;
    }


    /**
     * 2、传入头节点，翻转单项链表
     *
     * @param head
     * @return
     */
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 3、移除链表中等于值的节点
     * <p>
     * 例如：1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。
     *
     * @param head
     * @param num
     * @return
     */
    public static Node removeValue(Node head, int num) {

        // 从链表的头开始，舍弃掉开头的且连续的等于num的节点
        while (head != null) {
            if (head.value != num) {
                break;
            }
            head = head.next;
        }

        // head来到 第一个不需要删的位置
        Node pre = head;
        Node cur = head;

        // 快慢指针
        while (cur != null) {
            if (cur.value == num) { // 快指针cur向下滑动，如果值等于num，则暂时把下一个节点给慢指针的下一个指向。从而跳过等于num的节点
                pre.next = cur.next;
            } else { // cur此时到了不等于num的节点，则慢指针追赶上去。达到的效果就是等于num的节点都被删掉了
                pre = cur;
            }
            // 快指针向下滑动
            cur = cur.next;
        }
        return head;
    }

    /**
     * 4、打印两个有序链表的公共部分
     * 例如：head1: 1->2->3->3->4->5 head2: 0->0->1->2->3->3->7->9
     * 公共部分为：1 2 3 3
     *
     * @param head1
     * @param head2
     */
    public void printCommonPart(Node head1, Node head2) {

        System.out.println("Common Part: ");

        while (head1 != null && head2 != null) {
            if (head1.value < head2.value) {
                head1 = head1.next;
            } else if (head1.value > head2.value) {
                head2 = head2.next;
            } else {
                System.out.println(head1.value);
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        System.out.println();
    }

    /**
     * 5、删除单链表的倒数第k个节点
     *
     * @param head
     * @param lastKth
     * @return
     */
    public Node removeLastKthNode(Node head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }

        // cur指针也指向链表头节点
        Node cur = head;
        // 检查倒数第lastKth个节点的合法性
        while (cur != null) {
            lastKth--;
            cur = cur.next;
        }

        // 需要删除的是头结点
        if (lastKth == 0) {
            head = head.next;
        }

        if (lastKth < 0) {
            // cur回到头结点
            cur = head;
            while (++lastKth != 0) {
                cur = cur.next;
            }
            // 次吃cur就是要删除的前一个节点。把原cur.next删除
            cur.next = cur.next.next;
        }

        // lastKth > 0的情况，表示倒数第lastKth节点比原链表程度要大，即不存在
        return head;
    }

    /**
     * 6、删除链表中间节点
     * 思路：如果链表为空或者只有一个节点，不做处理。链表两个节点删除第一个节点，链表三个节点，删除中间第二个节点，链表四个节点，删除上中点
     *
     * @param head
     * @return
     */
    public Node removeMidNode(Node head) {
        // 无节点，或者只有一个节点的情况，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 链表两个节点，删除第一个节点
        if (head.next.next == null) {
            return head.next;
        }

        Node pre = head;
        Node cur = head.next.next;

        // 快慢指针
        if (cur.next != null && cur.next.next != null) {
            pre = pre.next;
            cur = cur.next.next;
        }

        // 快指针走到尽头，慢指针奇数长度停留在中点，偶数长度停留在上中点。删除该节点
        pre.next = pre.next.next;

        return head;
    }

    /**
     * 7、给定一个链表，如果成环，返回成环的那个节点
     * <p>
     * 思路：
     * 1. 快慢指针fast和slow，开始时，fast和slow都指向头节点，fast每次走两步，slow每次走一步
     * 2. 快指针向下移动的过程中，如果提前到达null，则链表无环，提前结束
     * 3. 如果该链表成环，那么fast和slow一定在环中的某个位置相遇
     * 4. 相遇后，立刻让fast回到head头结点，slow不动，fast走两步改为每次走一步。fast和slow共同向下滑动，再次相遇，就是成环节点
     *
     * @param head
     * @return
     */
    public Node getLoopNode(Node head) {
        // 节点数目不足以成环，返回不存在成环节点
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        Node n1 = head.next; // slow指针
        Node n2 = head.next.next; // fast指针

        while (n1 != n2) {
            // 快指针提前到达终点，该链表无环
            if (n2.next == null || n2.next.next == null) {
                return null;
            }

            n2 = n2.next.next;
            n1 = n1.next;
        }

        // 确定成环，n2回到头节点
        n2 = head;

        while (n1 != n2) {
            n2 = n2.next;
            n1 = n1.next;
        }

        // 再次相遇节点，就是成环节点
        return n1;
    }

    /**
     * 由于单链表，两个链表相交要不然两个无环链表相交，最后是公共部分；要不然两个链表相交，最后是成环部分
     * <p>
     * 8、判断两个无环链表是否相交，相交则返回相交的第一个节点
     * <p>
     * 思路：
     * 1. 链表1从头结点遍历，统计长度，和最后节点end1
     * 2. 链表2从头结点遍历，统计长度，和最后节点end2
     * 3. 如果end1不等一end2则一定不相交，如果相等则相交，算长度差，长的链表遍历到长度差的长度位置，两个链表就汇合在该位置
     *
     * @param head1
     * @param head2
     * @return
     */
    public Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;

        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }

        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }

        // 最终没汇聚，说明两个链表不相交
        if(cur1 != cur2) {
            return null;
        }

        cur1 = n > 0 ? cur1 : cur2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);

        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }

        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        return cur1;

    }

    /**
     * 9、合并两个有序链表
     * @param head1
     * @param head2
     * @return
     */
    public Node mergeTwoList(Node head1, Node head2) {
        // base case
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        // 选出两个链表较小的头作为整个合并后的头结点
        Node head = head1.value <= head2.value ? head1 : head2;
        // 链表1的准备合并的节点，就是头结点的下一个节点
        Node cur1 = head.next;
        // 链表2的准备合并的节点，就是另一个链表的头结点
        Node cur2 = head == head1 ? head2 : head1;

        // 最终要返回的头结点，预存为head，使用引用拷贝的pre向下移动
        Node pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.value <= cur2.value) {
                pre.next = cur1;
                // 向下滑动
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                // 向下滑动
                cur2 = cur2.next;
            }
            // pre向下滑动
            pre = pre.next;
        }

        // 有一个链表耗尽了，没耗尽的链表直接拼上
        pre.next = cur1 != null ? cur1 : cur2;
        return head;
    }
}
```