常用于链表复制,和链表一些操作。
可以不破坏原来链表,同时在上面进行操作。
例题
1,剑指Offer 35. 复杂链表的复制
题目
运用拆接-拆分法,可以使得random始终可以获取到原节点的random。
解法
/*
// 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 head;
Node cur = head;
while(cur!=null){
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
cur = cur.next.next;
}
Node pre1 = head;
while(pre1!=null){
if(pre1.random!=null){
pre1.next.random = pre1.random.next;
}
pre1 = pre1.next.next;
}
pre1 = head.next;
Node pre2 = head.next;
cur = head;
while(cur!=null){
if(cur.next!=null)
cur.next = cur.next.next;
else
cur.next = null;
if(pre2.next!=null){
pre2.next = pre2.next.next;
pre2 = pre2.next;
}
cur = cur.next;
}
return pre1;
}
}
解法分为三步。
- 给每个节点身后复制一个和源节点一样的(除了random),比如1->2->3变成1->1′->2->2′->3->3’。
- 为’节点赋值random.next。
- 将链表拆成原链表和新链表(因为原链表一般要求不能破坏),返回新链表。
正文完