CopyList

题目描述[原题链接][https://www.acwing.com/problem/content/89/]

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

• 函数结束后原链表要与输入时保持一致

算法描述

一共分三部分处理：

• 在当前链表每个结点后面复制一个一模一样的结点
• 遍历一遍链表找到每个结点的random指针的指向，复刻下来
• 将复制出来的链表分离出来

做题时一定要注意细节的处理，每个循环的出口都要注意

C++代码

/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
       for(auto p = head;p;){
           auto q = new ListNode(p->val);
           auto m = p->next;
           p->next = q;
           q->next = m;
           p = m;
       }
       
       for(auto p = head;p;p=p->next->next){
           if(p->random)
                p->next->random=p->random->next;
       }
       
       auto dummy = new ListNode(-1);
       auto curr = dummy;
       for(auto p = head;p;p=p->next){
           curr->next = p->next;
           curr = p->next;
           p->next = p->next->next;
       }
       return dummy->next;
    }
};

Java代码

/**
 * Definition for singly-linked list with a random pointer.
 * class ListNode {
 *     int val;
 *     ListNode next, random;
 *     ListNode(int x) { this.val = x; }
 * };
 */
class Solution {
    public ListNode copyRandomList(ListNode head) {
        if(head==null)return null;
        ListNode p = head;
        ListNode t; 
        while(p!=null){
            ListNode q=new ListNode(p.val);
            t=p.next;
            p.next=q;
            q.next=t;
            p=t;
        }
        p=head;
        while(p!=null){
            if(p.random!=null)
                p.next.random=p.random.next;
            p=p.next.next;
        }
        p=head;
        ListNode dummy=new ListNode(-1);
        t=dummy;
        while(p!=null){
           t.next=p.next;
           t=p.next;
           if(p.next!=null&&p.next.next!=null)
                p.next=p.next.next;
            else p.next=null;
           p=p.next;
        }
        return dummy.next;
    }
}