复杂链表的复制

题目:

请实现函数RandomListNode chose(RandomListNode head),复制一个复杂链表。在复杂链表中,每个节点除了有一个m pNext指针指向下一个节点,还有一个m pSibling 指针指向链表中的任意节点或者ullpr. 节点的C++定义如下:


主要思路:

提示:这里可以添加要学的内容
例如:
1、 将复制的节点放在被复制节点的后面;
方法:
2、 设置复制后的节点得指向
3、 奇数位是原来得链表,偶数位是复制后的链表;只要将奇数位和偶数位的节点分别链接起来,返回偶数位节点的头结点,那么就可以解决问题了


代码调试:

class RandomListNode {     int label;     RandomListNode next = null;     RandomListNode random = null;      RandomListNode(int label) {         this.label = label;     }  }   public class Main {     public static void main(String[] args) {         RandomListNode head = new RandomListNode(1);         RandomListNode node1 = new RandomListNode(2);         RandomListNode node2= new RandomListNode(3);         RandomListNode node3 = new RandomListNode(4);         RandomListNode node4= new RandomListNode(5);         head.next =node1;         node1.next = node2;         node2.next = node3;         node3.next=node4;         head.random = node2;         node1.random = node4;         RandomListNode node = Clone(head);         while (node!=null){             System.out.print(node.label+" ");          if(node.random!=null){              System.out.println("指向"+node.random.label);          }             node = node.next;         }       }      public  static  RandomListNode Clone(RandomListNode pHead) {              CloneNodes(pHead);              ConnectsitNodes(pHead);              return  chose(pHead);     }      //第一步:把复制得N‘ 放在N后     public  static void CloneNodes(RandomListNode head){         RandomListNode node = head;         while (node!=null){             RandomListNode clond = new RandomListNode(0);             clond.label = node.label;             clond.next = node.next;             clond.random = null;             node.next = clond;             node = clond.next;         }     }      //第二步设置复制出来的结点的random     public  static void ConnectsitNodes(RandomListNode head){         RandomListNode node = head;         while (node!=null){             RandomListNode clond = node.next;             if(node.random!=null){                 clond.random = node.random.next;             }             node = clond.next;         }      }     //把长链表拆分成两个链表,把奇数位置的节点和偶数位置上节点用next链接起来     public  static RandomListNode chose(RandomListNode head){         RandomListNode node = head;         RandomListNode pclondhead = null;         RandomListNode pclondnode = null;         if(node!=null){             pclondhead = pclondnode = node.next;             node.next = pclondnode.next;             node = node.next;         }         while(node!=null){             pclondnode.next = node.next;             pclondnode = pclondnode.next;             node.next = pclondnode.next;             node = node.next;         }         return pclondhead;     }  }  

运行结果:

复杂链表的复制

版权声明:玥玥 发表于 2021-06-04 0:29:58。
转载请注明:复杂链表的复制 | 女黑客导航