Subject to introduce

Force buckle 138: leetcode-cn.com/problems/co…

Analysis of the

In addition to each node having a pointer to the next node, there is an additional pointer to any node in the linked list or null, as shown in the following figure:

How to copy a linked list with random Pointers?

We can first ignore the Random pointer, then copy each node of the original linked list, append to the original node, and then copy the Random pointer. Finally, we split the original list and the copy list, and restore the original list.

The process is shown as follows:

1. Append each node with its copy, and join the original list with the copy list.

2. Each original linked list node is traversed from front to back. For node P with random pointer, we make its p->next->random = P ->random->next, so that we complete the copy of the original linked list random pointer.

3. Finally, we split the original list and the copy list, and restore the original list.

The specific process is as follows:

  • 1. Define a p pointer that iterates through the list, copying each node, and concatenating the original list with the replicated list.
  • 2, iterate through the list again, execute p->next->random = p->random->next, copy the random pointer.
  • Dummy is used to point to the head node of the replicated linked list, split the two lists and restore the original list.

The code is as follows:

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }} * /

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }

        // Copy each node and join the original and replicated lists together.
        for(Node p = head; p ! =null; p = p.next.next) {
            Node q = new Node(p.val);
            q.next = p.next;
            p.next = q;
        }

        // Copy the random pointer
        for(Node p = head; p ! =null; p = p.next.next) {
            if(p.random ! =null) { p.next.random = p.random.next; }}// Split two lists, and restore the original list, dummy nodes
        Node dummy = new Node(-1);
        Node cur = dummy;
        for(Node p = head; p ! =null; p = p.next) {
            Node q = p.next;
            cur.next = q;
            cur = cur.next;
            p.next = q.next;
        }
        returndummy.next; }}Copy the code

Time complexity analysis: O(n), where n is the length of the linked list.

Space complexity analysis: O(1).