35. Replication of complex linked lists

“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Hi 👋

• Wechat: RyukieW
• Wechat official account: LabLawliet
• 📦 Archive of technical articles
• 🐙 making

More columns:

The independent development of Lawliet

Lawliet’s iOS garden party

Lawliet’s underlying iOS lab

Lawliet’s iOS Reverse lab

Lawliet’s brush book

The title

Implement the function copyRandomList to copy a complex linked list. In complex linked lists, each node has a next pointer to the next node and a random pointer to any node in the list, or null.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Example 2:

Input: head = [[1,1],[2,1]]

Output: [[1, 1], [2, 1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]

Output: [[3, null], [3, 0], [3, null]]

Example 4:

Enter: head = []

Output: []

Explanation: The given linked list is null (null pointer), so null is returned.

Tip:

-10000 <= Node.val <= 10000

Node.random is null or points to a Node in the list.

The number of nodes does not exceed 1000.

Attention: leetcode-cn.com/problems/co…

Source: LeetCode

Answer key

func copyRandomList2(_ head: ComplexListNode) -> ComplexListNode? {
    var p: ComplexListNode? = head
    
    // A a B b C c D d
    while let current = p {
        let node = ComplexListNode(current.val)
        node.next = current.next
        p?.next = node
        p = current.next?.next
    }
    
    / / deal with the random
    p = head
    while let current = p {
        let clone = current.next
        clone?.random = current.random?.next
        p = clone?.next
    }
    
    // Delete the original node
    let result: ComplexListNode? = head.next
    p = result
    while let current = p {
        p?.next = current.next?.next
        p = p?.next
    }
    
    return result
}
Copy the code

👋 Welcome to like and follow ♥️