题目:
请实现函数ComplexListNode Clone(ComplexListNode head),复制一个复杂链表。在复杂链表中,每个结点除了有一个Next指针指向下一个结点外,还有一个Sibling指向链表中的任意结点或者NULL。
思路:
- 在每个节点后插入要复制的节点
- 复制节点间的连接关系
- 拆解成两个链表
代码:
static class ListNode{
int val;
ListNode next;
ListNode sibling;
ListNode(int val){
this.val=val;
}
}
private static ListNode copyList(ListNode a) {
copy(a);//第一步
copySecondLink(a);//第二步
return copySep(a);//第三步
}
private static ListNode copySep(ListNode node) {
ListNode head=node;
ListNode newHead=null;
ListNode newNode=null;
if (head!=null){
newHead=newNode=head.next;
head.next=newNode.next;
head=head.next;
}
while (head!=null){
newNode.next=head.next;
newNode=newNode.next;
head.next=newNode.next;
head=head.next;
}
return newHead;
}
private static void copySecondLink(ListNode node) {
ListNode a=node;
while (a!=null){
if (a.sibling!=null){
a.next.sibling=a.sibling.next;
}
a=a.next.next;
}
}
private static void copy(ListNode node) {
ListNode a=node;
while (a!=null){
ListNode tmp=a.next;
ListNode newNode=new ListNode(a.val);
newNode.next=tmp;
a.next=newNode;
a=tmp;
}
}
网友评论