AcWing 48. 复杂链表的复刻 -最新Java实现(正确提交)
原题链接
中等
作者:
锦鱼不忘旧时晨
,
2021-01-30 12:33:56
,
所有人可见
,
阅读 739
Java代码
/**
* Definition for singly-linked list with a random pointer.
* class ListNode {
* int val;
* ListNode next, random;
* ListNode(int x) { this.val = x; }
* };
*/
/*
1、首先给链表中的每个点后面加上这个点的复制
2、遍历整个链表,有random点的节点,p.next.random=p.random.next;
3、拆分出新的链表(注意要恢复原链表)
*/
class Solution {
public ListNode copyRandomList(ListNode head) {
if(head == null) return null;
ListNode p = head;
//复制原始节点,插在对应原始节点之后
while(p!=null){
ListNode ne = new ListNode(p.val);
ListNode next=p.next;
p.next=ne;
ne.next=next;
p=next;
}
//复制random节点,原始节点的下一个节点为复制节点,要想找该节点的random的复制,就要找原始节点random的下一个
p = head;
while(p!=null){
if(p.random!=null)
p.next.random = p.random.next;
p = p.next.next;
}
//拆分
ListNode res = new ListNode(-1);
ListNode q = res;
p = head;
while(p!=null){
q.next=p.next;
q=q.next;
p.next=p.next.next;//恢复原链表的操作
p=p.next;
}
return res.next;
}
}
p.next=p.next.next;//恢复原链表的操作 类似这种操作不需要考虑p.next空指针吗
可读性强!