【算法&数据结构体系篇class09】：链表问题：快慢指针、回文结构、复制、中点，分区、相交

秒速五厘米 2024-03-26 13:26 4阅读 0赞

### 一、链表解题的方法论 ###

> 1)对于笔试，不用太在乎空间复杂度，一切为了时间复杂度  
>   
> 2)对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

### 二、链表常用数据结构和技巧 ###

> 1）使用容器(哈希表、数组等)  
>   
> 2）快慢指针

### 三、快慢指针 ###

> 1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点  
>   
> 2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点  
>   
> 3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个  
>   
> 4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

**代码演示：**

package class09;
    
    import java.util.ArrayList;
    
    public class LinkedListMid {
        public static class Node{
            public int value;
            public Node next;
            public Node(int value){
                this.value = value;
            }
        }
    
        /**链表求各种中点问题：
         * 1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
         *
         * 2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
         *
         * 3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
         *
         * 4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
         */
        //1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点 比如[2->3->5->6] 返回3节点
         public static Node midOrUpMidNode(Node head){
             //特殊情况：如果节点个数小于3个
             if(head == null || head.next == null || head.next.next == null){
                 return head;
             }
             //节点3个及以上
             Node slow = head.next;
             Node fast = head.next.next;
             while(fast.next != null && fast.next.next != null){
                 slow = slow.next;
                 fast = fast.next.next;
             }
             return slow;
         }
    
          //2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点 比如[2->3->5->6] 返回5节点
        public static Node midOrDownMidNode(Node head){
             //如果头节点空 或者只有头节点 就返回头节点
             if(head == null || head.next ==null){
                 return head;
             }
             //快慢指针都同步来到头节点的下节点。这样进行指针前移，当前到边界时 slow就能确保在符合题意的位置
             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;
        }
    
        //3）输入链表头节点，奇数长度返回中点前一个， 偶数长度返回上中点前一个 比如[2->3->5] 返回2节点 比如[2->3->5->6] 返回2节点
        public static Node midOrUpMidPreNode(Node head){
             //假如空节点，只有头节点 只有两个节点 这些情况下，都是返回溢出的节点，统一返回null
             if(head == null || head.next == null || head.next.next ==null){
                 return null;
             }
             //有三个及以上节点时
            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;
        }
    
        //4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个 比如[2->3->5] 返回2节点 比如[2->3->5->6] 返回3节点
        public static Node midOrDownMidPreNode(Node head){
             //当空  只有头节点  那么就是返回溢出的节点 直接返回Null
             if(head == null || head.next == null){
                 return null;
             }
             Node slow = head;
             Node fast = head.next;
             while(fast.next != null && fast.next.next != null){
                 slow = slow.next;
                 fast = fast.next.next;
             }
             return slow;
        }
    
        public static Node right1(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            ArrayList<Node> arr = new ArrayList<>();
            while (cur != null) {
                arr.add(cur);
                cur = cur.next;
            }
            return arr.get((arr.size() - 1) / 2);
        }
    
        public static Node right2(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            ArrayList<Node> arr = new ArrayList<>();
            while (cur != null) {
                arr.add(cur);
                cur = cur.next;
            }
            return arr.get(arr.size() / 2);
        }
    
        public static Node right3(Node head) {
            if (head == null || head.next == null || head.next.next == null) {
                return null;
            }
            Node cur = head;
            ArrayList<Node> arr = new ArrayList<>();
            while (cur != null) {
                arr.add(cur);
                cur = cur.next;
            }
            return arr.get((arr.size() - 3) / 2);
        }
    
        public static Node right4(Node head) {
            if (head == null || head.next == null) {
                return null;
            }
            Node cur = head;
            ArrayList<Node> arr = new ArrayList<>();
            while (cur != null) {
                arr.add(cur);
                cur = cur.next;
            }
            return arr.get((arr.size() - 2) / 2);
        }
    
        public static void main(String[] args) {
            Node test = null;
            test = new Node(0);
            test.next = new Node(1);
            test.next.next = new Node(2);
            test.next.next.next = new Node(3);
            test.next.next.next.next = new Node(4);
            test.next.next.next.next.next = new Node(5);
            test.next.next.next.next.next.next = new Node(6);
            test.next.next.next.next.next.next.next = new Node(7);
            test.next.next.next.next.next.next.next.next = new Node(8);
    
            Node ans1 = null;
            Node ans2 = null;
    
            ans1 = midOrUpMidNode(test);
            ans2 = right1(test);
            System.out.println(ans1 != null ? ans1.value : "无");
            System.out.println(ans2 != null ? ans2.value : "无");
    
            ans1 = midOrDownMidNode(test);
            ans2 = right2(test);
            System.out.println(ans1 != null ? ans1.value : "无");
            System.out.println(ans2 != null ? ans2.value : "无");
    
            ans1 = midOrUpMidPreNode(test);
            ans2 = right3(test);
            System.out.println(ans1 != null ? ans1.value : "无");
            System.out.println(ans2 != null ? ans2.value : "无");
    
            ans1 = midOrDownMidPreNode(test);
            ans2 = right4(test);
            System.out.println(ans1 != null ? ans1.value : "无");
            System.out.println(ans2 != null ? ans2.value : "无");
    
        }
    }

### 四、给定一个单链表的头节点head，请判断该链表是否为回文结构。 ###

***题意：比如 12321 12344321从左往右读 跟从右往左读是一样的***

> 核心思路：  
> 1）栈方法特别简单（笔试用）  
>   
> 2）改原链表顺序的方法就需要注意边界了（面试用）

**代码演示：**

package class09;
    
    import java.util.Stack;
    
    /**
     * 给定一个单链表的头节点head，请判断该链表是否为回文结构。
     * 比如 12321   12344321从左往右读 跟从右往左读是一样的
     */
    public class IsPalindromeList {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int v) {
                value = v;
            }
        }
    
        //额外空间O(N) 用入栈出栈， 出栈顺序即为反序
        public static boolean isPalindrome1(Node head) {
            if (head == null || head.next == null) return true;
            //定义一个栈存链表元素
            Stack<Node> stack = new Stack<>();
            Node cur = head;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
                if (stack.pop().value != cur.value) {
                    return false;
                }
                cur = cur.next;
            }
            return true;
        }
    
        //额外空间O(N/2) 用入栈出栈， 入栈后一半元素，然后与前一半比较 出栈顺序即为反序
        public static boolean isPalindrome2(Node head) {
            if (head == null || head.next == null) return true;
            //使用快慢指针，让慢指针落到中点，如果是偶数个 那么就落到下中点，12344321 即落到第二个4 ,1111 第三个1， 11，第二个1
            //如果时奇数个，那么就落在中点下个节点  1234321 即落到第二个3
            //这两种不管怎么落，就从当前指针往后的元素入栈，最后依次出栈与头节点比较。 只要是回文结构都是相等的。
            Node slow = head.next;
            Node fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            //后半段元素入栈
            Stack<Node> stack = new Stack<>();
            while (slow != null) {
                stack.push(slow);
                slow = slow.next;
            }
            //利用快指针内存重定向头节点
            fast = head;
    
            while (!stack.isEmpty()) {
                if (stack.pop().value != fast.value) {
                    return false;
                }
                fast = fast.next;
            }
            return true;
        }
    
        //额外空间O(1) 反转原链表后半段，与前半段对比，最后再把后半段链表还原，即再反转
        public static boolean isPalindrome3(Node head) {
            if (head == null || head.next == null) return true;
            Node n1 = head;
            Node n2 = head;
            //1.快慢指针找到中点，如果是偶数 那么中点就落在了中点上节点  12344321 落在第一个4
            while (n2.next != null && n2.next.next != null) {
                n1 = n1.next;
                n2 = n2.next.next;
            }
            //2. 定义n2重定向在n1中点下节点 12344321 落在第二个4  1234321 落在第二个3
            n2 = n1.next;
            //3.将上中点的next指针指向null, 这样做是为了与后半链表循环比较时有跳出循环的条件。
            n1.next = null;
            Node n3 = null;//辅助变量保存下个节点
            while (n2 != null) {
                n3 = n2.next;
                n2.next = n1;
                n1 = n2;
                n2 = n3;
            }
            //4.跳出循环时n1则落在最后一个节点 1->2->3->4 <- 4<-3<-2<-1 最后的1，将n2从定向在head节点 开始头尾比较相等
            n2 = head;
            //5.注意要保存n1节点在n3  最后还需要将其顺序反转回原链表顺序
            n3 = n1;
            //6.遍历n1 n2 头尾节点 如果是回文结构那么肯定相等，否则返回false 因为此时第一个4.next=null。判断到中点则会跳出循环
            while (n1 != null && n2 != null) {
                if (n1.value != n2.value) return false;
                n1 = n1.next;
                n2 = n2.next;
            }
            //7.此时如果符合，那么最后就是将后面 44321反转 在利用前面指针变量进行反转
            //可以提前先将下个指向保存，然后最后一个元素n3指向为空，形成4 <- 4<-3<-2 1
            n1 = n3.next; //cur
            n3.next = null;  //pre
            while(n1 != null){
                n2 = n1.next; //利用n2保存下一个元素
                n1.next = n3;
                n3 = n1;
                n1 = n2;
            }
            return true;
        }
    
        public static void printLinkedList(Node node) {
            System.out.print("Linked List: ");
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            Node head = null;
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(2);
            head.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(2);
            head.next.next.next.next = new Node(1);
            printLinkedList(head);
            System.out.print(isPalindrome1(head) + " | ");
            System.out.print(isPalindrome2(head) + " | ");
            System.out.println(isPalindrome3(head) + " | ");
            printLinkedList(head);
            System.out.println("=========================");
    
        }
    
    }

### 五、将单向链表按某值划分成左边小、中间相等、右边大的形式 ###

> 核心思路：  
> 1）把链表放入数组里，在数组上做partition（笔试用）  
>   
> 2）分成小、中、大三部分，再把各个部分之间串起来（面试用）

package class09;
    
    import class08.TrieTree;
    
    /**
     * 将单向链表按某值划分成左边小、中间相等、右边大的形式
     *
     * 1）把链表放入数组里，在数组上做partition
     *
     * 2）分成小、中、大三部分，再把各个部分之间串起来
     */
    public class SmallerEqualBigger {
        public static class Node{
            public int value;
            public Node next;
            public Node(int v) {value = v;}
        }
    
        //1）把链表放入数组里，在数组上做partition  额外空间复杂度O(N)
        //数组做好分区操作，就遍历节点 依次重新指向下节点，注意最后一个节点要指向NULL
       public static Node listPartition1(Node head, int pivot){
            if(head == null) return head;
            //定义辅助变量遍历链表 判断链表大小
           Node cur = head;
           int size = 0;
           while(cur != null){
               size++;
               cur = cur.next;
           }
           cur = head; //重新指向头节点
           //定义数组存放节点
           Node[]nodeArr = new Node[size];
           for (int i = 0;i<nodeArr.length;i++){
               nodeArr[i] = cur;
               cur = cur.next;
           }
           //进行partition分区操作，按pivot值做划分
           partition(nodeArr,pivot);
           //节点重新定于指向，按照排好序的数组
            for(int i =1;i<nodeArr.length;i++){
                nodeArr[i-1].next = nodeArr[i];
            }
            //最后的节点的next指向注意要指向null
           nodeArr[nodeArr.length-1].next = null;
            return nodeArr[0];
       }
    
        public static void partition(Node[] nodeArr, int pivot) {
            int less = -1;
            //注意大于区边界，是从最右元素+1的边界开始，因为这里划分值不是最后一个元素，需要一起判断
            int big = nodeArr.length;
            int index = 0;
            //开始分区交换，直到下标索引遇到右侧的大于区左边界big就停止
            while(index < big){
                if(nodeArr[index].value < pivot){
                    swap(nodeArr,++less,index++);
                }else if(nodeArr[index].value == pivot){
                    index++;
                }else {
                    swap(nodeArr,--big,index);
                }
            }
        }
        public static void swap(Node[] arr,int i,int j){
            Node temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        //2）分成小、中、大三部分，再把各个部分之间串起来 额外复杂度三个区间有限变量 O(1)
        根据题意分成三个区间，定义小于区[sH,ST]、等于区[eH,eT]、大于区[mH,mT]，每个区间都有头尾
        //最好分别把对应的值填入三个区间链表，再将小于区尾 -> 等于区头 -> 大于区头 指向起来。
        public static Node listPartition2(Node head, int pivot){
            if(head == null) return null;
            Node sH = null;
            Node sT = null;
            Node eH = null;
            Node eT = null;
            Node mH = null;
            Node mT = null;
            Node next = null;  //辅助变量保存下个指向节点
            //开始将节点放入到三个链表中
            while (head != null){
                next = head.next; //保存下个节点
                head.next = null;  //清空指向节点 赋值为null,后面后依次进行重新排序指向
                if(head.value < pivot){
                    //当前值小于划分值，就进入小于区 假如小于区没有头节点 说明是第一个节点 直接赋值头尾
                    if(sH==null){
                        sH = head;
                        sT = head;
                    }else{ //如果存在区间有值，那么就接在后面，保持原链表的稳定性 顺序次序不变
                        sT.next = head;
                        sT = head;
                    }
                    //等于就放入等于区间链表
                }else if(head.value == pivot){
                    if(eH == null){
                        eH = head;
                        eT = head;
                    }else{
                        eT.next = head;
                        eT = head;
                    }
                }else{//大于就放入大于区间链表
                    if(mH == null){
                        mH = head;
                        mT = head;
                    }else{
                        mT.next = head;
                        mT = head;
                    }
                }
                //当前节点判断放哪个链表区间后，就接着指向下个节点
                head = next;
            }
            //放完三个链表区间后，要进行三个链表的指向，注意边界判断：
            // 假设小于区头节点不为空，那么就表示右小于区值，尾部指向等于区头部，此时等于区是否为空，都不影响
            if(sH != null){
                sT.next = eH;
                //接下来就是要连接大于区间，但是需要判断是小于区连接还是等于区，有可能等于区为空，那就是小于区连接大于区
                //如果等于区头不为空，那么eT还是eT,保持不变进行连接大于区的头，假如为空，那么就需要赋值成小于区的尾部，进行连接大于区的头
                eT = eT != null? eT : sT; //谁连接大于区头 谁就是eT
            }
    
            // 下一步，一定是需要用eT 去接 大于区域的头
            // 有等于区域，eT -> 等于区域的尾结点
            // 无等于区域，eT -> 小于区域的尾结点
            // eT 尽量不为空的尾巴节点
            if(eT != null){
                eT.next = mH; //非空则将eT指向大于区头
            }
            //连接完成，但是返回要判断头是否为空
            //如果小于区头非空 那么就返回sH,如果空，
            //就判断等于区头是否空，如果非空，那么就返回eH,如果空，
            //就返回大于区头mH
            return sH != null? sH:(eH!=null)?eH:mH;
        }
    
        public static void printLinkedList(Node node) {
            System.out.print("Linked List: ");
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head1 = new Node(7);
            head1.next = new Node(9);
            head1.next.next = new Node(1);
            head1.next.next.next = new Node(8);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(2);
            head1.next.next.next.next.next.next = new Node(5);
            printLinkedList(head1);
            // head1 = listPartition1(head1, 4);
            head1 = listPartition2(head1, 5);
    
            printLinkedList(head1);
            Node head2 = new Node(7);
            head2.next = new Node(9);
            head2.next.next = new Node(1);
            head2.next.next.next = new Node(8);
            head2.next.next.next.next = new Node(5);
            head2.next.next.next.next.next = new Node(2);
            head2.next.next.next.next.next.next = new Node(5);
            printLinkedList(head2);
            head2 = listPartition1(head2, 5);
            printLinkedList(head2);
        }
    }

### 六、138. 复制带随机指针的链表 ###

[138. 复制带随机指针的链表][138.]

![8f5fa50a7e498f90d90d469d1c3a6afb.png][]

![7b6f36776035a774d10c05b02c285cb8.png][]

![c5dc14456fe3254b3e3cc12962cda1e8.png][]

> **核心思路：**  
> 1.通过哈希表保存节点，老节点为key,新节点为value 然后依次进行赋值next和random指针  
> 这里特殊点在于random是随机指向，第一个可以指向最后一个，所以需要先获取出全部元素 再进行赋值  
> 2.不使用哈希表的方式，减少空间复杂度，可以将复制的节点，依次放到对应节点的nex指针下 比如：  
> 1->2->3->4 => 1-> copy1 -> 2 -> copy2 -> 3 -> copy3 -> 4 -> copy4，然后调整random指针，最后就将新老节点next指向分离出来 恢复原链表 返回复制链表头节点

package class09;
    
    import java.util.HashMap;
    
    /**
     * 一种特殊的单链表节点类描述如下
     * class Node {
     * int value;
     * Node next;
     * Node rand;
     * Node(int val) { value = val; }
     * }
     * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
     * 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
     * 【要求】
     * 时间复杂度O(N)，额外空间复杂度O(1)
     */
    public class CopyListWithRandom {
        public static class Node{
            public int val;
            public Node next;
            public Node random;
            public Node(int v){
                val = v;
                next = null;
                random = null;
            }
        }
    
        //通过哈希表保存节点，老节点为key,新节点为value 然后依次进行赋值next和random指针
        //这里特殊点在于random是随机指向，第一个可以指向最后一个，所以需要先获取出全部元素 再进行赋值
        public static Node copyRandomList1(Node head){
            if(head == null)return null;
            //定义哈希表，保存节点，key对应的就是一个复制的节点
            HashMap<Node,Node> map = new HashMap<>();
            Node cur = head;
            while (cur != null){
                //每次进行遍历赋值新生成一个对应节点
                map.put(cur,new Node(cur.val));
                cur = cur.next;
            }
            //节点生成好之后就是赋值next random指针。
            //map.get(node).next   新节点 next=》 map.get(node.next) node.next表示老节点的next。 通过map获取得到新节点next
            cur = head;
            while(cur != null){
                //新节点cur map.get(cur)的next指向 就是对应老节点cur的next指向，cur.next。 其指向对应的新节点就是map.get(cur.next)
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }
    
        //不使用哈希表的方式，减少空间复杂度，可以将复制的节点，依次放到对应节点的nex指针下 比如：
        //1->2->3->4 => 1-> copy1 -> 2 -> copy2 -> 3 -> copy3 -> 4 -> copy4
        public static Node copyRandomList2(Node head){
            if(head == null) return null;
            Node cur = head;
            Node next = null;
            //将复制节点，都依次放到对应老节点的next   1-> copy1 -> 2 -> copy2 -> 3 -> copy3 -> 4 -> copy4
            while(cur != null){
                // 1-->2   把copy1放到两者中间 1 -> copy1 >2
                next = cur.next;
                cur.next = new Node(cur.val);
                cur.next.next = next;
                cur = next;
            }
            cur = head;
            //先将节点的random指针调整好
            while (cur != null){
                //1-> copy1 ->2 注意保存原节点的next 2
                next = cur.next.next;
                //cur.next.random新节点的random指向  就是cur.random老节点的指向一致，对应的是再其next，cur.random.next
                cur.next.random = cur.random != null?cur.random.next:null;
                cur = next;
            }
    
            //最后分离出新老节点next指向
            cur = head;
            //新节点的头节点
            Node ans = head.next;
            //新节点遍历指针
            Node newNode = null;
            while(cur != null){
                //新节点的next
                next = cur.next.next;
                //当前对应的新节点
                newNode = cur.next;
                //分离新节点  旧节点next指向之前自己的next
                cur.next = next;
                //新节点next 分离 指向自己的next 也就是对应老节点的next
                newNode.next = next!=null?next.next:null;
                cur = next;
            }
            return ans;
        }
    }

### 七、*给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null* ###

***【要求】***

***\* 如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。***

> **核心思路**：  
> 空间复杂度如果不限制，那么可以将两链表保存在数组，然后依次从头遍历如果有相等的就表示首个相交点  
> *\* 1.分类进行判断 两个链表都没有环，那么相交节点往后的节点肯定都是一样的。不可能后面还交叉，节点只有一个next*  
> *\* 就可以判断如果相交了 那么最后两链表节点是肯定相等的 。确定相交后，再判断两个链表长度，较长的链表减去两链表长度差值*  
> *\* 后开始与较短的链表同时遍历，一旦相等，就是相交第一个节点*  
> *\* 2.两个链表一个有环，一个没环，那么肯定是没有相交的节点的 没有这种符合链表结构，因为一定会出现有节点存在两个next指针*  
> *\* 3.两个链表有环，那相交节点 会存在两种形式。*  
> *\* 两个链表环节点1即第一个相交点（这里也有可能相交节点也是入环首节点，判断逻辑都一样 ）， 另一种就是 1 2 都可以认为是第一相交节点*  
> *\* 第一种如两链表长度不同，那么就较长的链表减去两链表长度差值，后开始与较短的链表同时遍历，一旦相等，就是相交第一个节点*  
> *\* 第二种就是以一个链表的入环节点1.next节点开始遍历，直到走回入环节点，过程遇到另外一个链表的入环节点2则表示相交。返回1或2都认为是相交首节点*  
>  *\* \* \* \**  
>  *\* \* \* \**  
> ***1*** ***1***  *\** ***2***  
>  *\* \* \**  
>  *\* \* \* \* \**  
>  *\* \* \**

**代码演示**：

package class10;
    
    
    /**
     * 给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
     * 【要求】
     * 如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
     * <p>
     * 思路：(空间复杂度如果不限制，那么可以将两链表保存在数组，然后依次从头遍历如果有相等的就表示首个相交点)
     * 1.分类进行判断 两个链表都没有环，那么相交节点往后的节点肯定都是一样的。不可能后面还交叉，节点只有一个next
     * 就可以判断如果相交了 那么最后两链表节点是肯定相等的 。确定相交后，再判断两个链表长度，较长的链表减去两链表长度差值
     * 后开始与较短的链表同时遍历，一旦相等，就是相交第一个节点
     * 2.两个链表一个有环，一个没环，那么肯定是没有相交的节点的 没有这种符合链表结构，因为一定会出现有节点存在两个next指针
     * 3.两个链表有环，那相交节点 会存在两种形式。
     * 两个链表环节点1即第一个相交点（这里也有可能相交节点也是入环首节点，判断逻辑都一样 ）， 另一种就是 1 2 都可以认为是第一相交节点
     * 第一种如两链表长度不同，那么就较长的链表减去两链表长度差值，后开始与较短的链表同时遍历，一旦相等，就是相交第一个节点
     * 第二种就是以一个链表的入环节点1.next节点开始遍历，直到走回入环节点，过程遇到另外一个链表的入环节点2则表示相交。返回1或2都认为是相交首节点
     * *     *             *           *
     *   *   *               *         *
     *     1                   1  *  2
     *     *                 *         *
     *  *    *                 *   *  *
     *  *  *  *
     */
    public class FindFirstIntersectNode {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int v) {
                value = v;
            }
        }
    
        //判断两链表是否相交，相交则返回第一个节点 不相交就返回null
        public static Node getIntersectNode(Node head1, Node head2) {
            if (head1 == null || head2 == null) return null;
            //获取两链表的入环首节点 无环则返回null
            Node loop1 = getLoopNode(head1);
            Node loop2 = getLoopNode(head2);
            //判断 两链表没有环   两链表都有环的两种情况
            if (loop1 == null && loop2 == null) {
                //没环的两个链表头节点入参进行获取相交首节点
                return noLoop(head1, head2);
            }
            if (loop1 != null && loop2 != null) {
                //有环的两个链表，需要将头节点 入环首节点都入参
                return bothLoop(head1, loop1, head2, loop2);
            }
            //如果是一个链表有环，一个链表无环，那么肯定没有相交节点 返回null
            return null;
        }
    
        //获取两个有环链表相交首节点，没有相交则返回null
        public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
            if(head1 == null || head2 == null) return null;
            //1.链表有环，那有两种情况
            //一个是两链表的入环首节点相等，那么将两链表等长位置开始往环首节点遍历过程如果有相等节点就表示相交首节点
            //另一个是入环首节点不相等，两个环节点都是相交首节点 返回哪个都可以
            if(loop1 == loop2){
                //如果入环首节点相交
                Node cur1 = head1;
                Node cur2 = head2;
                int n = 0;
                //定义较长链表与较短链表，这里注意 只需要遍历到loop 环节点，因为环内都是相同节点不需遍历
                while(cur1 != loop1){
                    cur1 = cur1.next;
                    n++;
                }
                while(cur2 != loop2){
                    cur2 = cur2.next;
                    n--;
                }
                cur1 = n > 0? head1:head2;
                cur2 = cur1 ==head1?head2:head1;
                //确定好长短链表 就将长链表cur1先走n步 再两链表同时走，相遇即为相交首节点 n要取绝对值
                n = Math.abs(n);
                while(n!=0){
                    //递减差值直到0 较长链表cur1节点就来到和cur2同长节点
                    n--;
                    cur1 = cur1.next;
                }
                //遍历一定会存在一个相等节点 为相交首节点
                while(cur1 != cur2){
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                }
                //相遇则返回其中一个节点即可
                return cur1;
            }else {
                //两链表入环首节点不相交 链表结构就是两个入环节点都是相交首节点
                //判断是否相交，就先遍历其中一个链表入环节点.next，绕一圈退出，假如有节点是与另外一个链表的入环节点一致 就表示相交 返回任意两链表一个入环节点
                Node cur = loop1.next;
                while(cur != loop1){
                    //假如节点中有与head2链表的入环节点loop2相等 那么就表示有相交，返回相交节点就是两链表任意一个入环节点
                    if(cur == loop2){
                        return loop1;
                    }
                    cur = cur.next;
                }
            }
            //如果没相交 返回null
            return null;
        }
    
        //获取两个无环链表相交首节点，没有相交则返回null
        public static Node noLoop(Node head1, Node head2) {
            if (head1 == null || head2 == null) return null;
            Node cur1 = head1;
            Node cur2 = head2;
            int n = 0;    //定义变量保存链表长度
            //1.先遍历head1
            while (cur1 != null) {
                n++;
                cur1 = cur1.next;
            }
            //2.再遍历head2 同时将head1的长度n 递减 看看最后n值 如果是大于0 那么表示head1链表较长
            while (cur2 != null) {
                n--;
                cur2 = cur2.next;
            }
            //3.两链表来到了最后节点，此时判断 如果两链表有相交节点，那么两链表的尾节点一定相等的，因为不可能相交后又交叉出去，链表节点只有一个next
            if (cur1 != cur2) return null;
            //4.走到这里表示链表有相交，重定义cur1为较长的链表  cur2是较短的链表 假如n=0,两遍链表相等 等长不用交换
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            //4.将较长链表cur1先减去 差值n 需要取绝对值，假如n=0,那么就不用减，两链表直接从头节点开始遍历肯定会有相等的首节点
            n = Math.abs(n);
            while (n != 0) {
                cur1 = cur1.next;
                n--;
            }
            //5.执行完差值后 两链表cur1 cur2就开始往后等长，同时遍历 相遇时则是相交首节点
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            //6.最后返回相交首节点
            return cur1;
        }
    
        //获取链表入环第一个节点 如果没环返回null
        public static Node getLoopNode(Node head) {
            if (head == null || head.next == null || head.next.next == null) return null;
            Node slow = head;
            Node fast = head;
            //先把快慢指针调整一次，下面的while条件才能执行起来 否则一开始都是头节点会存在相同情况
            slow = slow.next;
            fast = fast.next.next;
            //1.快慢指针遍历直到相遇
            while (slow != fast) {
                //如果快指针指向空 则表示链表没有环 那么就需要返回null
                if (fast.next == null || fast.next.next == null) return null;
                slow = slow.next;
                fast = fast.next.next;
            }
            //2.快指针或慢指针其一重新指向头节点 然后再同步长进行指向，一旦快慢指针相等就表示来到入环的第一个节点
            fast = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    
    
        public static void main(String[] args) {
            // 1->2->3->4->5->6->7->null
            Node head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            head1.next.next.next = new Node(4);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(6);
            head1.next.next.next.next.next.next = new Node(7);
    
            // 0->9->8->6->7->null
            Node head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next.next.next.next.next; // 8->6
            System.out.println(getIntersectNode(head1, head2).value);
    
            // 1->2->3->4->5->6->7->4...
            head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            head1.next.next.next = new Node(4);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(6);
            head1.next.next.next.next.next.next = new Node(7);
            head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
    
    
            // 0->9->8->2...
            head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next; // 8->2
            System.out.println(getIntersectNode(head1, head2).value);
    
            // 0->9->8->6->4->5->6..
            head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next.next.next.next.next; // 8->6
            System.out.println(getIntersectNode(head1, head2).value);
    
        }
    }

### 八、不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉 ###

比如 1 -> 2 -> 3 -> 4 -> 5 ,链表 要删除指定节点，3， 但是不给链表头节点：

> 思路：  
> 拿到的是指定的节点3位置， 可以将节点3.val = 节点3.next ，也就是3改成4数值。变成：  
>  1 -> 2 -> 4 -> 4 -> 5  
> 然后将节点3.next删除， 节点3.next = 节点3.next.next,变成：   
>  1 -> 2 -> 4 ->5

[138.]: https://leetcode.cn/problems/copy-list-with-random-pointer/
[8f5fa50a7e498f90d90d469d1c3a6afb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6f7813de50824c6dbc22144a95840878.png
[7b6f36776035a774d10c05b02c285cb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b260e0e8b1f44dd3b514216aa7960aae.png
[c5dc14456fe3254b3e3cc12962cda1e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/dba475637bc54b4e9b8b799f0efd8fdf.png