【剑指offer-Java版】26复杂链表的复制

蔚落 2022-08-21 09:40 84阅读 0赞

复杂链表复制：

一种思路是通过哈希表存放sibling的配对信息 – 没看明白  
一种思路是直接在原始链表中复制，然后拆分 – 属于时间和空间效率都比较高的方式  
分三步，还是比较好懂的

public class _Q26<T> {
    
        public ComplexListNode<T> Clone(ComplexListNode<T> list){
    
            if(list == null) return null;
    
            CloneNodes(list);
            ConnectSibling(list);
            return ReconnectedNodes(list);
        }
    
        private void CloneNodes(ComplexListNode<T> list){
            ComplexListNode<T> nextNode = list;
    
            while(nextNode != null){
    
                ComplexListNode<T> node = new ComplexListNode<>();
    
                node.value = nextNode.value;
                node.next = nextNode.next;
                nextNode.next = node;
    
                nextNode = nextNode.next.next; // 复制之后也是需要 一次走两步的
            }
        }
    
        private void ConnectSibling(ComplexListNode<T> list){
            ComplexListNode<T> nextNode = list;
    
            while(nextNode != null){
                if(nextNode.sibling != null){
                    nextNode.next.sibling = nextNode.sibling.next;
                }
                nextNode = nextNode.next.next; // 一次跨两步
            }
        }
    
        private ComplexListNode<T> ReconnectedNodes(ComplexListNode<T> list){
    
            ComplexListNode<T> result = list.next;
    
            ComplexListNode<T> node1 = list;
            ComplexListNode<T> node2 = result;
    
            while(node2 != null){
    
                if(node2.next == null){
                    node1.next = null;
                }else{
                    node1.next = node2.next;
                    node2.next = node2.next.next;
                }
    
                node1 = node1.next;
                node2 = node2.next;
            }
    
            return result;
        }
        }

测试代码：

public class _Q26Test extends TestCase {
    
        _Q26 cloneComplexList = new _Q26();
    
        public void test(){
            ComplexListNode<Character> list = new ComplexListNode<>();
            ComplexListNode<Character> node1 = new ComplexListNode<>();
            ComplexListNode<Character> node2 = new ComplexListNode<>();
            ComplexListNode<Character> node3 = new ComplexListNode<>();
            ComplexListNode<Character> node4 = new ComplexListNode<>();
    
            list.value = 'A';
            node1.value = 'B';
            node2.value = 'C';
            node3.value = 'D';
            node4.value = 'E';
    
            list.next = node1;
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = null;
    
            list.sibling = node2;
            node1.sibling = node4;
            node3.sibling = node1;
    
            System.out.println("===================================before");
            ComplexListNode<Character> node = list;
            while(node != null){
                System.out.println(node.value + " - " + (node.sibling == null ? "" : node.sibling.value));
                node = node.next;
            }
    
            ComplexListNode<Character> result = cloneComplexList.Clone(list);
    
            System.out.println("===================================after");
            ComplexListNode<Character> nodeX = result;
            while(nodeX != null){
                System.out.println(nodeX.value + " - " + (nodeX.sibling == null ? "" : nodeX.sibling.value));
                nodeX = nodeX.next;
            }
        }
        }