单链表时间复杂度 有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表展开称一级单链表

有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表展开称一级单链表  

这个二级单链表只包括一些head public class Link { public Link Next; public int Data; public Link(Link next int data) { this Next = next; this Data = data; } } public class CascadeLink { public Link Next; public CascadeLink NextHead; public CascadeLink(CascadeLink nextHead Link next) { this Next = next; this NextHead = nextHead; } }

下面做一个二级单链表 GenerateLink 和GenerateLink 方法在前面都已经介绍过了 public static CascadeLink GenerateCascadeLink() { Link head = GenerateLink (); Link head = GenerateLink (); Link head = GenerateLink (); CascadeLink element = new CascadeLink(null head ); CascadeLink element = new CascadeLink(element head ); CascadeLink element = new CascadeLink(element head ); CascadeLink head = new CascadeLink(element null); return head; } 就是说 这些单链表的表头head head head head …… 它们组成了一个二级单链表head null –> head –> head –> head –> head –>

我们的算法思想是 进行两次遍历 在外层用curr 遍历二级单链表head 在内层用curr 遍历每个单链表 public static Link GenerateNewLink(CascadeLink head) { CascadeLink curr = head NextHead; Link newHead = curr Next; Link curr = newHead; while (curr != null) { curr Next = curr Next Next; while (curr Next != null) { curr = curr Next; } curr = curr NextHead; } return newHead; }