程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode_Copy List with Random Pointer

leetcode_Copy List with Random Pointer

編輯:C++入門知識

leetcode_Copy List with Random Pointer


描述:

 

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路:

1.首先根據舊鏈表的值創建一個新的鏈表並分別將舊鏈表和新鏈表存儲到listOld和listNew中。

2.然後根據舊鏈表中index位置的結點的random指針所指向的位置,找出舊鏈表指針所指向結點在listOld中的index,也即listNew中的newIndex

3.把新鏈表中的index位置的結點指向newIndex位置的結點,問題得解!

代碼:

 

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
		if(head==null)
			return null;
		ListlistOld=new ArrayList();//store the old node
		ListlistNew=new ArrayList();//store the new node
		RandomListNode newHead=new RandomListNode(0);
		RandomListNode pListNode=head,curListNode=newHead;
        while(pListNode!=null)//create the new LinkList && store the old node to listOld&store the new node to listNew 
        {
        	listOld.add(pListNode);//store the old node
        	RandomListNode qListNode=new RandomListNode(pListNode.label	);
        	listNew.add(qListNode);//store the new node
        	curListNode.next=qListNode;
        	curListNode=qListNode;
        	pListNode=pListNode.next;
        }
        RandomListNode qListNode=newHead.next,temp=null;
        pListNode=head;
        int indexOld=0;
        while(pListNode!=null)//get the index of pListNode.random ,then put the node of indexOld to che random of the current newList
        {
        	temp=pListNode.random;
        	if(temp!=null)
        	{
        		indexOld=listOld.indexOf(pListNode.random);//get the index of pListNode.random
            	qListNode.random=listNew.get(indexOld);//put the node of indexOld to che random of the current newList
        	}
        	else {
				qListNode.random=null;
			}
        	pListNode=pListNode.next;
        	qListNode=qListNode.next;
        }
        
        return newHead.next;
    }
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved