数据结构与算法之复制含有随机指针节点的链表和两个链表相交的一系列问题

朴灿烈づ我的快乐病毒、 2021-12-21 02:05 120阅读 0赞

# 数据结构与算法复制含有随机指针节点的链表和两个链表相交的一系列问题 #

--------------------

## 目录 ##

1.  复制含有随机指针节点的链表
2.  两个链表相交的一系列问题

--------------------

### 1. 复制含有随机指针节点的链表 ###

1.  题目概述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]
2.  思路：创建一个HashMap结构，key放当前Node，value放需要复制的Node。
3.  代码实现

import java.util.HashMap;
    
    public class Code_CopyListWithRandom {
        
    
        public static class Node {
        
            public int value;
            public Node next;
            public Node rand;
    
            public Node(int data) {
        
                this.value = data;
            }
        }
    
        public static Node copyListWithRand1(Node head) {
        
            HashMap<Node, Node> map = new HashMap<Node, Node>();
            Node cur = head;
            while (cur != null) {
        
                map.put(cur, new Node(cur.value));
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
        
                map.get(cur).next = map.get(cur.next);
                map.get(cur).rand = map.get(cur.rand);
                cur = cur.next;
            }
            return map.get(head);
        }
    
        public static Node copyListWithRand2(Node head) {
        
            if (head == null) {
        
                return null;
            }
            Node cur = head;
            Node next = null;
            // copy node and link to every node
            while (cur != null) {
        
                next = cur.next;
                cur.next = new Node(cur.value);
                cur.next.next = next;
                cur = next;
            }
            cur = head;
            Node curCopy = null;
            // set copy node rand
            while (cur != null) {
        
                next = cur.next.next;
                curCopy = cur.next;
                curCopy.rand = cur.rand != null ? cur.rand.next : null;
                cur = next;
            }
            Node res = head.next;
            cur = head;
            // split
            while (cur != null) {
        
                next = cur.next.next;
                curCopy = cur.next;
                cur.next = next;
                curCopy.next = next != null ? next.next : null;
                cur = next;
            }
            return res;
        }
    
        public static void printRandLinkedList(Node head) {
        
            Node cur = head;
            System.out.print("order: ");
            while (cur != null) {
        
                System.out.print(cur.value + " ");
                cur = cur.next;
            }
            System.out.println();
            cur = head;
            System.out.print("rand:  ");
            while (cur != null) {
        
                System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            Node head = null;
            Node res1 = null;
            Node res2 = null;
            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(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(4);
            head.next.next.next.next = new Node(5);
            head.next.next.next.next.next = new Node(6);
    
            head.rand = head.next.next.next.next.next; // 1 -> 6
            head.next.rand = head.next.next.next.next.next; // 2 -> 6
            head.next.next.rand = head.next.next.next.next; // 3 -> 5
            head.next.next.next.rand = head.next.next; // 4 -> 3
            head.next.next.next.next.rand = null; // 5 -> null
            head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
    
            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(head);
            System.out.println("=========================");
    
        }
    
    }

--------------------

### 2. 两个链表相交的一系列问题 ###

###### 1. 题目描述 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]

###### 2. 思路 ######

1.  得到入环节点：
    
    1.  如果节点个数为0,1，2，那么不能形成环，返回null。
    2.  设置两个节点node1，node2，node1为慢节点，一次走一步，node2为快节点，一次走两步
    3.  遍历链表，如果可以相交即为有环
    4.  将node2重新置为head节点，一次走一步，重新从头节点出发，遇到node1即为入环节点
    5.  可以自行测试
2.  无环链表相交问题
    
    1.  如果head1或head2一方为null，则不会相交，返回null
    2.  创建cur1和cur2节点，n变量。其中，cur1指向head1节点，cur2指向head2节点，n记录两个链表的长度。
    3.  判断cur1和cur2是否相同，即最后一个节点如果不相同，则不会相交。
    4.  遍历head1，每走一步n++，遍历head2，每走一步n–。最后得到的n值即为两个链表的长度差。
    5.  复用cur1和cur2，当n>0时，说明head1比较长，将cur1指向head1，否则head2比较长，将cur1，指向head2。cur2指向短的链表head1或head2。将n取绝对值。
    6.  cur1先走n步，跟cur2一样长时，两者一起走，当两者值一样时即为无环链表相交点。返回cur1即可。  
        ![在这里插入图片描述][20190628115306855.png]
3.  有环链表相交问题
    
    1.  创建两个变量cur1，cur2.
    2.  **如果两个入环节点相同**，则将head1赋给cur1，head2赋给cur2.创建一个变量n记录head1和head2的长度。
    3.  遍历head1，每走一步n++，遍历head2，每走一步n–。最后得到的n值即为两个链表的长度差。
    4.  复用cur1和cur2，当n>0时，说明head1比较长，将cur1指向head1，否则head2比较长，将cur1，指向head2。cur2指向短的链表head1或head2。将n取绝对值。
    5.  cur1先走n步，跟cur2一样长时，两者一起走，当两者值一样时即为无环链表相交点。返回cur1即可。
    6.  **如果两个入环节点不同**，则可能相交也可能不相交。
    7.  使cur1 = loop1.next，遍历环结构，如果途中遇到loop2，即为相交，否则不相交。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]

###### 3. 代码实现 ######

public class Code_FindFirstIntersectNode {
        
    
        public static class Node {
        
            public int value;
            public Node next;
    
            public Node(int data) {
        
                this.value = data;
            }
        }
    
        public static Node getIntersectNode(Node head1, Node head2) {
        
            if (head1 == null || head2 == null) {
        
                return 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);
            }
            return null;
        }
    
        //得到入环节点
        public static Node getLoopNode(Node head) {
        
            if (head == null || head.next == null || head.next.next == null) {
        
                return null;
            }
            Node n1 = head.next; // n1 -> slow
            Node n2 = head.next.next; // n2 -> fast
            while (n1 != n2) {
        
                if (n2.next == null || n2.next.next == null) {
        
                    return null;
                }
                n2 = n2.next.next;
                n1 = n1.next;
            }
            n2 = head; // n2 -> walk again from head
            while (n1 != n2) {
        
                n1 = n1.next;
                n2 = n2.next;
            }
            return n1;
        }
    
        //无环链表相交问题
        public static 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 ? head1 : head2;
            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;
        }
    
    //    两个有环链表相交问题
        public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        
            Node cur1 = null;
            Node cur2 = null;
            if (loop1 == loop2) {
        
                cur1 = head1;
                cur2 = head2;
                int n = 0;
                while (cur1 != loop1) {
        
                    n++;
                    cur1 = cur1.next;
                }
                while (cur2 != loop2) {
        
                    n--;
                    cur2 = cur2.next;
                }
                cur1 = n > 0 ? head1 : head2;
                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;
            } else {
        
                cur1 = loop1.next;
                while (cur1 != loop1) {
        
                    if (cur1 == loop2) {
        
                        return loop1;
                    }
                    cur1 = cur1.next;
                }
                return null;
            }
        }
    
        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);
    
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211221/efd7e6b7094746c18456c5b10739824f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211221/3d27ec4949be4645a9fc2709a7001eb1.png
[20190628115306855.png]: /images/20211221/4d73184eff1442b49307152fecf38a49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: /images/20211221/ef318644bdde4688a9625124e9ee94d9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关如果两个单链表相交，输出相交节点

文章目录如果两个单链表相交，输出相交节点一、实现二、输出如果两个单链表相交，输出相交节点一、实现

秒速五厘米/ 2023年02月09日 11:52/ 0 赞/ 13 阅读

相关 [数据结构与算法]两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） function FindFirs

痛定思痛。/ 2022年12月12日 15:05/ 0 赞/ 78 阅读

相关【链表】 LeetCode138. 复制带随机指针的链表

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

心已赠人/ 2022年12月02日 13:38/ 0 赞/ 103 阅读

相关 138. 复制带随机指针的链表

> 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表

￡神魔★判官ぃ/ 2022年10月18日 01:52/ 0 赞/ 111 阅读

相关数据结构与算法--两个链表中第一个公共节点

链表中第一个公共节点公节点定义：同一个节点在两个链表中，并不是节点值相同题目：输入两个节点，找出他们的第一个公共节点，节点定义如需 / 链表元

左手的ㄟ右手/ 2022年10月07日 01:57/ 0 赞/ 85 阅读

相关链表问题——复制含有随机指针节点的链表

【题目】　　一种特殊的链表节点类描述如下：　　 class Node { public int value; pu

小鱼儿/ 2022年06月03日 03:55/ 0 赞/ 132 阅读

相关链表问题_两个链表的第一个公共节点

题目：输入两个链表，找出它们的第一个公共结点分析：对于这个问题有三种思路： 1、蛮力算法，当遍历到一个节点时，就在另外一个链表上顺序遍历，并且判断是否相等，如果想等就

喜欢ヅ旅行/ 2022年05月21日 04:17/ 0 赞/ 172 阅读

相关判断两个单链表是否相交，若相交，求节点（链表不带环）

先理解一下题目的意思，单链表的相交和普通两条线的相交一样吗？ ![在这里插入图片描述][70] 所以当我们把其换成节点就可以变成下面这样： ![在这里插入图片描述][

﹏ヽ暗。殇╰゛Y/ 2022年05月11日 00:56/ 0 赞/ 204 阅读

相关带有随机指针链表的复制

链表复制上次介绍了关于链表的相交与求环问题，这次我来给大家介绍一个让我脑瓜子嗡嗡的复杂链表的复制问题。。说实话，链表也太狂野了，太会玩了，都快赶上苏大强了。。。。。。

曾经终败给现在/ 2022年02月17日 05:42/ 0 赞/ 162 阅读

相关数据结构与算法之复制含有随机指针节点的链表和两个链表相交的一系列问题

数据结构与算法复制含有随机指针节点的链表和两个链表相交的一系列问题 -------------------- 目录 1. 复制含有随机指针节点的链表 2. 两

朴灿烈づ我的快乐病毒、/ 2021年12月21日 02:05/ 0 赞/ 121 阅读