Shulou(Shulou.com)06/02 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.