复制复杂链表O(n)时间复杂度

时间:2022-02-13 17:14:25

struct Node

{

int m_key;

Node *m_next;

Node *m_random;

};

            _________

           |                    ↑

A —> B —>C —>D

|________↑



1、在每一个Node后边添加一个Node结点,变成:

                       ________________

                     |                                     ↓

A —> A' —>B —>B'—>C —>C'—>D—>D'

|_________________↑

2、N'的m_random指针指向N的m_random指针的m_next;

                                 ________________

                                |                                     ↓

A —> A' —>B —>B'—>C —>C'—>D—>D'

          |_________________↑

3、把偶数结点摘出来,复位原链表