企业建设网站的过程,title 镇江网站建设,门户网站流程图,五指山住房建设局网站请实现函数ComplexListNode* Clone(ComplexListNode * pHead),复制一个复杂链表。在复杂链表中#xff0c;每个结点除了有一个m_pNext指针指向下一个结点外#xff0c;还有一个m_pSibling指向链表中的任意结点或者NULL。结点的C定义如下#xff1a;
struct ComplexListNode…请实现函数ComplexListNode* Clone(ComplexListNode * pHead),复制一个复杂链表。在复杂链表中每个结点除了有一个m_pNext指针指向下一个结点外还有一个m_pSibling指向链表中的任意结点或者NULL。结点的C定义如下
struct ComplexListNode{ int m_nValue; ComplexListNode* m_pNext; ComplexListNode* m_pSibling; }; 上图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针虚线箭头表示m_pSibling指针。为了简单起见指向NULL的指针没有画出。 思路
第一步制原始链表上的每个结点N创建N然后把这些创建出来的结点用m_pNext链接起来。同时我们把N, N的配对信息放到一个哈希表中。第二步还是设置复制链表上的每个结点的m_pSibling。如果在原始链表中结点N的m_pSibling指向结点S那么在复制链表中对应的N应该指向S。由于有了哈希表我们可以在O(1)的时间根据S找到S’。这种是以O(n)的空间换来了On的时间复杂度。
代码
package offer;
import java.util.HashMap; import java.util.Map;
class ComplexList { char val; ComplexList next null; ComplexList extend null; ComplexList(char val) { this.val val; } } public class ti35 { static ComplexList CloneComplexList(ComplexList head) { MapComplexList,ComplexList map new HashMapComplexList,ComplexList(); ComplexList CloneNode new ComplexList(a); if(head!null) { CloneNode head; map.put(head,CloneNode); } ComplexList CloneHead CloneNode; while(head.next!null) { head head.next; CloneNode CloneNode.next; map.put(head, CloneNode); } CloneNode CloneHead; while(CloneNode.next!null) { CloneNode.extend map.get(CloneNode.extend); CloneNode CloneNode.next; } return CloneHead; } public static void main(String[] args) { ComplexList a new ComplexList(A); ComplexList b new ComplexList(B); ComplexList c new ComplexList(C); ComplexList d new ComplexList(D); ComplexList e new ComplexList(E); a.next b; b.next c; c.next d; d.next e; b.extend e; a.extend c; d.extend b; ComplexList result CloneComplexList(a); while(result.next!null) { System.out.print(result.val result.next.val ); if(result.extend!null) { System.out.println(result.extend.val); } else { System.out.println(); } result result.next; } } } 不使用辅助空间
代码
static ComplexList CloneComplexList2(ComplexList head) { if(headnull) { return head; } ComplexList p head;//记录原来链表的头结点 while(head.next!null) { ComplexList x new ComplexList(head.val); x.next head.next; head.next x; head x.next; } ComplexList x new ComplexList(head.val); head.next x; head p; while(head.next.next!null) { if(head.extend!null) head.next.extend head.extend.next; head head.next.next; } head p; ComplexList q head.next,result;//记录克隆链表的头结点 result q; //System.out.println(q.val q.next.val); while(q.next!nullq.next.next!null) { //System.out.println(q.val q.next.val); q.next q.next.next; q q.next; } return result; }
