What is the replication method of Java complex linked list
Today, I would like to share with you the relevant knowledge of what the replication method of Java complex linked list is, the content is detailed, and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article.
The concept of complex linked lists:
In a complex linked list, each node has not only a _ pnext pointer to the next node, but also a _ pSibling to any node or NULL in the linked list.
The structure of each node in the complex linked list is as follows:
/ / the structure of complex chain table nodes
Template
Struct ComplexListNode
{
ComplexListNode ()
: _ pnext (NULL)
, _ pSibling (NULL)
{}
ComplexListNode (const T & x)
: _ pnext (NULL)
, _ pSibling (NULL)
, value (x)
{}
T value;// data
ComplexListNode* _ pnext;// points to the next node
ComplexListNode* _ pSibling;// points to any node
}
Replication of complex linked lists:
Method 1:
The first step is to copy each node of the linked list and link it with _ pnext; the second step is to set the _ pSibling of each node in the linked list. Suppose that the _ pSibling of a node N in the original linked list points to node S, and the position of S can be either before or after N, so to determine the location of S needs to start from the head node. If you find S through s steps along the _ pnext from the beginning, then the distance between the _ pSibling of the N' node on the replication list and the head node of the copy list is also along the step of the _ pnext pointer s. Because the pSibling of locating each node needs to go through the O (n) step from the head node, the time complexity is O (n ^ 2). It's a waste of time.
Method 2:
The first step is to copy each node of the linked list and link it with _ pnext; the second step is to set the _ pSibling of each node. If the _ pSibling of node N of the original linked list points to node S, then when copying the linked list, the corresponding N 'should point to S'. Because of the hash table, it takes O (1) time to find S 'according to S. This method trades space for time.
Method 3:
The first step is to create a new node corresponding to each node and connect it behind the original node.
Reference Code:
/ / create each new node pCloned to connect to the back of each original node
Template
Void ClonedNodes (ComplexListNode* pHead)
{
ComplexListNode* pNode = pHead
While (pNode! = NULL)
{
ComplexListNode* pCloned = new ComplexListNode (pNode- > value)
PCloned- > _ pnext = pNode- > _ pnext
PNode- > _ pnext = pCloned
PNode = pCloned- > _ pnext
}
}
The second step is to set the _ pSibling of the copied node, assuming that the An of the original linked list points to C, then the copied A 'corresponds to C'.
Reference Code:
/ / set the value of _ pSibling for each node copied out
Template
Void ConnectSiblingNodes (ComplexListNode* pHead)
{
ComplexListNode* pNode = pHead
While (pNode)
{
ComplexListNode* pCloned = pNode- > _ pnext
If (pNode- > _ pSibling! = NULL)
{
PCloned- > _ pSibling = pNode- > _ pSibling- > _ pnext
}
PNode = pCloned- > _ pnext
}
}
The third step is to split the linked list. The nodes in odd positions are linked with _ pnext to form the original linked list, and the nodes in even positions are linked with _ pnext to form a copied complex linked list.
Reference Code:
/ / splitting the merged linked list, linking the nodes at odd positions with _ pnext is the original linked list, and linking the nodes at even positions with _ pnext is the copied linked list.
Template
ComplexListNode* ReconnectNodes (ComplexListNode* pHead)
{
ComplexListNode* pNode = pHead
ComplexListNode* pClonedHead = NULL
ComplexListNode* pClonedNode = NULL
If (pNode! = NULL)
{
PClonedHead = pClonedNode = pHead- > _ pnext
PNode- > _ pnext = pClonedNode- > _ pnext
PNode = pNode- > _ pnext
}
While (pNode! = NULL)
{
PClonedNode- > _ pnext = pNode- > _ pnext
PClonedNode = pClonedNode- > _ pnext
PNode- > _ pnext = pClonedNode- > _ pnext
PNode = pNode- > _ pnext
}
Return pClonedHead
}
The combination of the above three steps is the complete process of replication.
/ / copy complex linked list functions
Template
ComplexListNode* Clone (ComplexListNode* pHead)
{
ClonedNodes (pHead)
ConnectSiblingNodes (pHead)
Return ReconnectNodes (pHead)
}
The test code is as follows:
Void test ()
{
ComplexListNode List1 (1.2)
ComplexListNode List2 (1.4)
ComplexListNode List3 (2.3)
ComplexListNode List4 (3.6)
ComplexListNode List5 (4.5)
List1._pnext = & List2
List2._pnext = & List3
List3._pnext = & List4
List4._pnext = & List5
List1._pSibling = & List3
List4._pSibling = & List2
List2._pSibling = & List5
ComplexListNode* pHead = Clone (& List1)
}
These are all the contents of the article "what is the replication method of Java complex linked list". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.
