[数据结构与算法]算法与数据结构08：链表问题

快慢指针

/**
 * 快慢指针
 */
public class LinkedList01 {

    /**
     * 输入链表头部，奇数长度返回中点，偶数长度返回上中点
     * @param head
     * @return
     */
    public static Node find01(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 输入链表头部，奇数长度返回中点，偶数长度返回下中点
     * @param head
     * @return
     */
    public static Node find02(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node slow = head.next;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 输入链表头部，奇数长度返回中点前一个，偶数长度返回上中点前一个
     * @param head
     * @return
     */
    public static Node find03(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node slow = head;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 输入链表头部，奇数长度返回中点前一个，偶数长度返回下中点前一个
     * @param head
     * @return
     */
    public static Node find04(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node slow = head;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }


    private static class Node {
        private Node next;
        private int value;
    }

}

四个类似的问题：
1、输入链表头部，奇数长度返回中点，偶数长度返回上中点
2、输入链表头部，奇数长度返回中点，偶数长度返回下中点
3、输入链表头部，奇数长度返回中点前一个，偶数长度返回上中点前一个
4、输入链表头部，奇数长度返回中点前一个，偶数长度返回下中点前一个

处理逻辑都一样，都是设置一个快指针和一个慢指针，快指针每次遍历两个结点，慢指针每次遍历一个结点，当快指针无法往后遍历时，返回慢指针指向的节点。
唯一不同的就是慢指针和快指针的初始指向。

输入一个链表头结点，判断链表是否是回文结构

/**
 * 输入一个链表头结点，判断链表是否是回文结构
 */
public class LinkedList02 {

    public static boolean isReverse01(Node head) {
        if (head == null && head.next == null)  return true;

        Stack<Node> stack = new Stack<>();
        Node help = head;
        //把链表中的所有结点压入栈中
        while (help != null) stack.push(help);
        boolean res = true;
        help = head;
        //此时从栈顶到栈底，结点顺序与链表相反，从链表头部开始遍历，每遍历一个节点，从栈中弹出一个进行比较
        while (!stack.isEmpty()) {
            res &= stack.pop().value == help.value;
            help = help.next;
        }
        return res;
    }

    public static boolean isReverse02(Node head) {
        if (head == null && head.next == null)  return true;

        //使用快慢指针，取到链表中点，只把链表后半部分压入栈中，与前半部分比较
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //把链表后半部分压入栈中
        Stack<Node> stack = new Stack<>();
        Node n2 = slow.next;
        boolean res = true;
        while (n2 != null) {
            stack.push(n2);
            n2 = n2.next;
        }

        //与前半部分比较
        n2 = head;
        while (!stack.isEmpty()) {
            res &= stack.pop().value == n2.value;
            n2 = n2.next;
        }

        return res;
    }

    public static boolean isReverse03(Node head) {
        if (head == null && head.next == null)  return true;

        //使用快慢指针，取到链表中点，把链表后半部分指针反转，然后与前半部分进行比较，笔记完毕后把指针还原
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //把链表后半部分指针反转
        Node n1 = slow;
        Node n2 = n1.next;
        n1.next = null;
        Node n3 = null;
        while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }

        //前后两半部分进行比较
        n3 = n1;
        n2 = head;
        boolean res = true;
        while (n1 != null && n2 != null) {
            res &= n1.value == n2.value;
            n1 = n1.next;
            n2 = n2.next;
        }

        //链表还原
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }

    private static class Node {
        private Node next;
        private int value;
    }

}

三种方法：
1、把链表结点压入栈中，此时栈中结点的顺序与链表相反，一个个弹出与链表结点比较即可
2、通过快慢指针，然慢指针指向链表中间节点，然后只把后半部分节点压入栈中，与列表节点进行比较，节省一半空间
3、通过快慢指针，然慢指针指向链表中间节点，然后把后把部分的节点的next指针反转，再用两个指针，一头一尾，遍历进行比较，比较完毕后还原后半部分节点的next指针

将单向链表按某值划分为左边小，中间等于，右边大于的形式

/**
 * 将单向链表按某值划分为左边小，中间等于，右边大于的形式
 */
public class LinkedList03 {

    public static Node partition01(Node head, int pivot) {
        if (head == null || head.next == null) return head;

        //计算链表大小，并创建对应大小的数组，临时存放链表结点
        Node help = head;
        int size = 0;
        while (help != null) {
            size++;
            head = help.next;
        }
        Node[] arr = new Node[size];
        help = help;
        int index = 0;
        while (help != null) {
            arr[index++] = help;
            help = help.next;
        }

        //根据pivot基准值，对数组做partition操作
        int i1 = -1; //(...i1] 小于区
        int i2 = 0; // (i1...i2] 等于区
        int i3 = arr.length; // (i2...i3]大于区
        while (i2 != i3) {
            Node curr = arr[i2];
            if (curr.value < pivot) {
                swap(arr, ++i1, i2++);
            } else if (curr.value > pivot) {
                swap(arr, i2, --i3);
            } else {
                i2++;
            }
        }

        //遍历数组，把结点串起来
        Node prev = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prev.next = arr[i];
            prev = arr[i];
        }

        return arr[0];
    }

    public static Node partition02(Node head, int pivot) {
        if (head == null || head.next == null) return head;

        Node smallHead = null; //小于区头结点
        Node smallTail = null; //小于区尾结点
        Node equalsHead = null; //等于区头结点
        Node equalsTail = null; //等于区尾结点
        Node bigHead = null; //大于区头结点
        Node bigTail = null; //大于区尾结点

        //遍历链表，组装小于区、等于区、大于区的链表，并且每遍历一个结点，就把原来的next指针断掉
        Node next;
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (smallHead == null) {
                    smallHead = head;
                    smallTail = head;
                } else {
                    smallTail.next = head;
                    smallTail = head;
                }
            } else if (head.value == pivot) {
                if (equalsHead == null) {
                    equalsHead = head;
                    equalsTail = head;
                } else {
                    equalsTail.next = head;
                    equalsTail = head;
                }
            } else {
                if (bigHead == null) {
                    bigHead = head;
                    bigTail = head;
                } else {
                    bigTail.next = head;
                    bigTail = head;
                }
            }
            head = next;
        }

        //小于区的尾部连接等于区的头部，等于区的头部连接大于区的头部，但是要判断边界情况，就是小于区、等于区有可能为空
        if (smallHead != null) {
            smallTail.next = equalsHead;
            equalsTail = equalsHead == null ? smallTail : equalsTail;
        }
        if (equalsHead != null) {
            equalsTail = bigHead;
        }
        return smallHead != null ? smallHead : (equalsHead != null ? equalsHead : bigHead);
    }

    private static class Node {
        private int value;
        private Node next;
    }

    private static void swap(Node[] arr, int i, int j) {
        Node temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

链表结点带rand指针克隆问题

/**
 * 链表结点带rand指针克隆问题
 */
public class LinkedList04 {

    public static Node clone01(Node head) {
        if (head == null) return null;

        //原结点 -> 克隆结点
        Map<Node, Node> map = new HashMap<>();

        //建立原结点与克隆结点的映射关系
        Node help = head;
        while (help != null) {
            Node copy = new Node();
            copy.value = help.value;
            map.put(help, copy);
            help = help.next;
        }

        //根据map中记录的原结点与克隆结点的映射关系，给克隆结点的next指针与rand指针赋值
        help = head;
        while (help != null) {
            Node copy = map.get(help);
            if (help.next != null) copy.next = map.get(help.next);
            if (help.rand != null) copy.rand = map.get(help.rand);
            help = help.next;
        }

        return map.get(head);
    }

    public static Node clone02(Node head) {

        //1、遍历列表，克隆结点，并把克隆结点连接到原结点后面
        //1->1`->2->2`->3->3`
        Node help = head;
        while (help != null) {
            Node next = help.next;
            Node copy = new Node();
            copy.value = help.value;
            help.next = copy;
            copy.next = next;
            help = next;
        }

        //2、遍历链表，处理克隆结点的rand指针
        help = head;
        while (help != null) {
            Node next = help.next.next;
            Node copy = help.next;
            if (help.rand != null) copy.rand = help.rand.next;
            help = next;
        }

        //3、链表分离
        Node res = help.next;
        help = head;
        while (help != null) {
            Node next = help.next.next;
            Node copy = help.next;
            help.next = next;
            if (next != null) copy.next = next.next;
            help = next;
        }

        return res;
    }

    private static class Node{
        private int value;
        private Node next;
        private Node rand;
    }

}

给定一个链表，如果有环则返回环中的第一个节点，没有则返回null

/**
 * 给定一个链表，如果有环则返回环中的第一个节点，没有则返回null
 */
public class LinkedList05 {

    public static Node find(Node head) {
        if (head == null || head.next == null || head.next.next == null) return null;

        //快慢指针，如果有环，两指针会在环中相遇
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        //让fast指针回到头结点，每一次走一步，快慢指针相遇的结点，就是环中第一个节点
        fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;

    }

    private static class Node {
        private int value;
        private Node next;
    }

}

给定两个无环链表，返回两个链表相交的第一个节点，没有则返回null

/**
 * 给定两个无环链表，返回两个链表相交的第一个节点，没有则返回null
 */
public class LinkedList06 {

    public static Node findIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) return null;

        //先遍历head1，计算head1长度
        int len = 0;
        Node curr1 = head1;
        while (curr1.next != null) {
            len++;
            curr1 = curr1.next;
        }

        //遍历head2，每遍历一个结点，len减一，计算出两个链表长度的差值
        Node curr2 = head2;
        while (curr2.next != null) {
            len--;
            curr2 = curr2.next;
        }

        //此时curr1和curr2都指向各自链表的尾结点，如果不是同一个尾结点，代表两链表没有相交，返回null
        if (curr1 != curr2) return null;

        //调整curr1和curr2指针，让cuur1指针指向长度较长的链表头结点
        curr1 = len < 0 ? head2 : head1;
        curr2 = curr1 == head1 ? head2 : head1;

        //此时len为两链表长度的差值，保证len为正数
        len = Math.abs(len);

        //curr1先走len步，使得curr1和curr2指向的结点开始到尾节点长度一样
        while (len != 0) {
            len--;
            curr1 = curr1.next;
        }

        //curr1和curr2每次各自走一步，最后必会到达相交处
        while (curr1 != curr2) {
            curr1 = curr1.next;
            curr2 = curr2.next;
        }

        return curr1;
    }

    private static class Node {
        private int value;
        private Node next;
    }

}

两个有环链表，给定链表头结点和环中第一个节点，找出两个链表相交的结点，没有相交则返回null

/**
 * 两个有环链表，给定链表头结点和环中第一个节点，找出两个链表相交的结点，没有相交则返回null
 */
public class LinkedList07 {

    public static Node findLoopIntersect(Node head1, Node loop1, Node head2, Node loop2) {
        Node curr1 = null;
        Node curr2 = null;
        // 第一种情况：两个链表在环外相交
        if (loop1 == loop2) {
            curr1 = head1;
            curr2 = head2;

            //遍历链表1，计算到入环结点的长度
            int len = 0;
            while (curr1 != loop1) {
                len++;
                curr1 = curr1.next;
            }

            //遍历链表二，也是到入环结点就停止，计算两个链表长度的差值
            while (curr2 != loop2) {
                len--;
                curr2 = curr2.next;
            }

            //调整curr1指向长度较长链表的头结点
            curr1 = len < 0 ? head2 : head1;
            curr2 = curr1 == head1 ? head2 : head1;

            //保证len为正数
            len = Math.abs(len);

            //curr1走len步，此时cuur1到入环结点与curr2到入环结点的长度相同
            while (len > 0) {
                len--;
                curr1 = curr1.next;
            }

            //curr1和curr2每次走1步，到入环结点或入环结点前必会相遇
            while (curr1 != curr2) {
                curr1 = curr1.next;
                curr2 = curr2.next;
            }

            return curr1;

        } else {
            //第二种情况，两个链表的入环结点不相同
            curr1 = loop1.next;
            //从loop1开始遍历链表1，看是否会与loop2相遇，是则两链表相交，返回loop1或loop2都可以，不会相遇则会回到loop1，返回null
            while (curr1 != loop1) {
                if (curr1 == loop2) return loop1;
                curr1 = curr1.next;
            }
            return null;
        }
    }

    private static class Node {
        private int value;
        private Node next;
    }

}

给定两个链表，有可能有环，也有可能无环，返回两个链表的相交结点，没有相交则返回null

/**
 * 给定两个链表，有可能有环，也有可能无环，返回两个链表的相交结点，没有相交则返回null
 */
public class LinkedList08 {

    public static Node find(Node head1, Node head2) {
        if (head1 == null || head2 == null) return null;

        //1、找出两个链表的入环结点
        Node loop1 = findLoopNode(head1);
        Node loop2 = findLoopNode(head2);

        //如果loop1和loop2都为null，则退化为寻找两个无环链表相交结点的问题
        if (loop1 == null && loop2 == null) {
            return findIntersectNodeNoLoop(head1, head2);
        }

        //如果loop1和loop2都不为空，则简化为寻找两个有环链表的相交结点问题
        if (loop1 != null && loop2 != null) {
            return findLoopIntersect(head1, loop1, head2, loop2);
        }

        //如果一个链表有环，一个链表无环，不可能相交，返回null
        return null;
    }

    /**
     * 找出两个有环链表的相交结点，没有则返回null
     * @param head1
     * @param loop1
     * @param head2
     * @param loop2
     * @return
     */
    public static Node findLoopIntersect(Node head1, Node loop1, Node head2, Node loop2) {
        Node curr1 = null;
        Node curr2 = null;
        // 第一种情况：两个链表在环外相交
        if (loop1 == loop2) {
            curr1 = head1;
            curr2 = head2;

            //遍历链表1，计算到入环结点的长度
            int len = 0;
            while (curr1 != loop1) {
                len++;
                curr1 = curr1.next;
            }

            //遍历链表二，也是到入环结点就停止，计算两个链表长度的差值
            while (curr2 != loop2) {
                len--;
                curr2 = curr2.next;
            }

            //调整curr1指向长度较长链表的头结点
            curr1 = len < 0 ? head2 : head1;
            curr2 = curr1 == head1 ? head2 : head1;

            //保证len为正数
            len = Math.abs(len);

            //curr1走len步，此时cuur1到入环结点与curr2到入环结点的长度相同
            while (len > 0) {
                len--;
                curr1 = curr1.next;
            }

            //curr1和curr2每次走1步，到入环结点或入环结点前必会相遇
            while (curr1 != curr2) {
                curr1 = curr1.next;
                curr2 = curr2.next;
            }

            return curr1;

        } else {
            //第二种情况，两个链表的入环结点不相同
            curr1 = loop1.next;
            //从loop1开始遍历链表1，看是否会与loop2相遇，是则两链表相交，返回loop1或loop2都可以，不会相遇则会回到loop1，返回null
            while (curr1 != loop1) {
                if (curr1 == loop2) return loop1;
                curr1 = curr1.next;
            }
            return null;
        }
    }

    /**
     * 找出两个无环链表的相交几点，没有则返回null
     * @param head1
     * @param head2
     * @return
     */
    public static Node findIntersectNodeNoLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) return null;

        //先遍历head1，计算head1长度
        int len = 0;
        Node curr1 = head1;
        while (curr1.next != null) {
            len++;
            curr1 = curr1.next;
        }

        //遍历head2，每遍历一个结点，len减一，计算出两个链表长度的差值
        Node curr2 = head2;
        while (curr2.next != null) {
            len--;
            curr2 = curr2.next;
        }

        //此时curr1和curr2都指向各自链表的尾结点，如果不是同一个尾结点，代表两链表没有相交，返回null
        if (curr1 != curr2) return null;

        //调整curr1和curr2指针，让cuur1指针指向长度较长的链表头结点
        curr1 = len < 0 ? head2 : head1;
        curr2 = curr1 == head1 ? head2 : head1;

        //此时len为两链表长度的差值，保证len为正数
        len = Math.abs(len);

        //curr1先走len步，使得curr1和curr2指向的结点开始到尾节点长度一样
        while (len != 0) {
            len--;
            curr1 = curr1.next;
        }

        //curr1和curr2每次各自走一步，最后必会到达相交处
        while (curr1 != curr2) {
            curr1 = curr1.next;
            curr2 = curr2.next;
        }

        return curr1;
    }

    /**
     * 找出链表入环结点，无环则返回null
     * @param head
     * @return
     */
    public static Node findLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) return null;

        //快慢指针，如果有环，两指针会在环中相遇
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        //让fast指针回到头结点，每一次走一步，快慢指针相遇的结点，就是环中第一个节点
        fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;

    }
    
    private static class Node {
        private int value;
        private Node next;
    }
    
}