cubegao

Swift.复杂链表的复制

2015-10-11

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。要求编写函数复制这个复杂链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import Foundation

// ListNode Utils
public class ComplexListNode {
    public var val: Int
    public var next: ComplexListNode?
    public var sibling: ComplexListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
        self.sibling = nil
    }
}

class For26Solution {
    func copyComplexListNode(_ head: ComplexListNode?) -> ComplexListNode {
        
        var p = copyNext(head)
            p = copySibling(p)
            p = partition(p)
        return p
    }
    
    //复制主链
    func copyNext(_ head: ComplexListNode?) -> ComplexListNode {
        
        var pNode = head
        let pHead = head


        while pNode != nil {
            
            let pClone = ComplexListNode(0)
            pClone.val = pNode!.val
            pClone.next = pNode?.next
            pClone.sibling = nil

            pNode?.next = pClone
            
            pNode = pNode?.next
        }
        
        return pHead!
    }
    
    //复制随机指针
    func copySibling(_ head: ComplexListNode?) -> ComplexListNode {
        
        var pNode = head
        let pHead = head
        
        
        while pNode != nil {
            
            let pClone = pNode!.next
            if pNode?.sibling != nil {
                pClone?.sibling = pNode?.sibling?.next
            }
            pNode = pClone?.next
            
        }
        
        return pHead!
    }
    
    //分离两个链表
    func partition(_ head: ComplexListNode?) -> ComplexListNode {
        
        var pNode = head
        var pCloneHead: ComplexListNode? = nil
        var pCloneNode: ComplexListNode? = nil
        
        if pNode != nil {
            pCloneHead = pCloneNode
            pCloneNode = pNode?.next
            pNode?.next = pCloneNode?.next
            pNode = pNode?.next
        }
        
        while pNode != nil {
            pCloneNode?.next = pNode?.next
            pCloneNode = pCloneNode?.next
            pNode?.next = pCloneNode?.next
            pNode = pNode?.next
        }
        
        return pCloneHead!
    }
}

算法思想：思想是在原来的链表每个节点后面都复制了一个同样的节点，再修改其指针，最后把偶数节点都抽出来，作为新的复杂链表。

github地址：https://github.com/cubegao/LeetCode

Tags: 算法
← Swift.二叉树中和为某一值的路径 Swift.二叉搜索树与双向链表 →

扫描二维码，分享此文章