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

This article mainly introduces "what is the method of copying C++ complex linked list". In daily operation, I believe that many people have doubts about the method of copying C++ complex linked list. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "what is the method of copying C++ complex linked lists". Next, please follow the editor to study!

Topic: please implement the function ComplexListNode* Clone (ComplextListNode* pHead) to copy a complex linked list. 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 C++ definition of a node is as follows:

Template

Struct ComplexListNode

{

T value

ComplexListNode* pNext

ComplexListNode* pSibling

}

As shown in the figure, the real arrow represents pNext and the virtual arrow represents pSibling.

(the main problem is to solve pSibling)

Plan 1: 1. Copy a new linked list according to pNext: A'-> baked-> clocked-> dashed-> E'.

2. Set the pSibling of each node of the new linked list

Every time, scan backward from the head of the original linked list, find the pSlibing from the corresponding point, write down the number of times, and then find the pSlibling of the new linked list according to this number.

For example, B-> E sets a count to scan from the beginning A to find out the number of interval nodes between B and E 3 according to the count

Set the pSibling of B'

The first disadvantage of option 1 is:

1. The solution of each node pSlibling is to find the time complexity O (n ^ 2) from scratch.

Plan 2: (optimization scheme 1, to solve the problem of large time complexity of pSlibling)

1. Set an index (hash table) to correspond the address of each node of the new table to the old table so that the new table node pointer can be found at O (1) time complexity according to the node pointer of the old table, so the total time complexity is O (n).

2. Scheme 2 uses one more table, and the space complexity is O (n), which is equivalent to trading space for time to reduce the time complexity from O (n ^ 2) to O (n).

Scheme 3: (relatively optimal optimization scheme 2): the time complexity O (n) is realized without auxiliary space.

1. Copy each node first, but link the new node to the back of the corresponding node in the original linked list

For example: a-> Aids-> B-> Bones-> C-> C-> D-> Downs-> E-> E'

2. A feature of this new and old integrated chain is that [the pSlibling of the new node is the pNext of the old node]

If A-> C, then A-> C'C'is the pNext of C.

3. After setting, the parity nodes are unlinked and separated from the new and old linked lists.

Option 3 code:

/ /-ComplexListNode.hpp-

# pragma once

/ / copy of complex linked list (complex linked list: there is also a pointer pSibling to other nodes in the linked list)

Template

Struct ComplexListNode

{

ComplexListNode ()

: pNext (NULL)

, pSibling (NULL)

{}

ComplexListNode (const T & v)

: pNext (NULL)

, pSibling (NULL)

, value (v)

{}

T value

ComplexListNode* pNext

ComplexListNode* pSibling;// randomly points to sibling nodes

}

/ * create each new node pCloned and link it to the corresponding original node pNode * /

Template

Void CloneNode (ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead

While (pNode! = NULL)

{

ComplexListNode* pCloned = new ComplexListNode (pNode- > value)

PCloned- > pNext = pNode- > pNext

PNode- > pNext = pCloned

PNode = pCloned- > pNext

}

}

/ * set the pSlibling value of the copied node * /

Template

Void ConnectSiblingNodes (ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead

While (pNode! = NULL)

{

ComplexListNode* pCloned = pNode- > pNext

If (pNode- > pSibling! = NULL)

{

/ / because pCloned is behind the corresponding pNode

/ / so the pSlibling of pCloned is also after the pSlibling of the corresponding pNode

/ / include situations where pNode points to you

PCloned- > pSibling = pNode- > pSibling- > pNext

}

PNode = pCloned- > pNext

}

}

/ * split the merged linked list (starting from 1) the original linked list is made up of the original list at the odd position and the new list is copied at the even position * /

Template

ComplexListNode* ReconnectNodes (ComplexListNode* pHead)

{

ComplexListNode* pNode = pHead

ComplexListNode* pClonedHead = NULL

ComplexListNode* pClonedNode = NULL

If (pNode! = NULL)

{

PClonedHead = pClonedNode = pNode- > pNext

PNode- > pNext = pClonedNode- > pNext

PNode = pNode- > pNext

}

While (pNode! = NULL) / / pNode is one more step than pClonedNode. If pNode is not empty, it means there is at least one pClonedNode after it.

{

PClonedNode- > pNext = pNode- > pNext

PClonedNode = pClonedNode- > pNext

PNode- > pNext = pClonedNode- > pNext

PNode = pNode- > pNext

}

Return pClonedHead

}

/ / copy complex linked list functions

Template

ComplexListNode* Clone (ComplexListNode* pHead)

{

CloneNode (pHead)

ConnectSiblingNodes (pHead)

Return ReconnectNodes (pHead)

}

/ /-test.cpp-

# define _ CRT_SECURE_NO_WARNINGS 1

# include

# include "ComplexListNode.hpp"

Using namespace std

Void testComplexListNode ()

{

ComplexListNode L1 (1)

ComplexListNode L2 (2)

ComplexListNode L3 (3)

ComplexListNode L4 (4)

ComplexListNode L5 (5)

L1.pNext = & L2

L2.pNext = & L3

L3.pNext = & L4

L4.pNext = & L5

/ / 1-> 2-> 3-> 4-> 5

/ / pSibling

/ / 2-> 2

L2.pSibling = & L2

/ / L3-> L1

L3.pSibling = & L1

/ / L5-> L1

L5.pSibling = & L1

ComplexListNode* Head2 = Clone & L1

}

Int main ()

{

TestComplexListNode ()

Return 0

}

At this point, the study of "what is the method of copying C++ complex linked list" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.