复杂链表复制代码java 链表的复制

将有序线性表La={2,4,6,7,9},Lb={1,5,7,8},合并为Lc={1,2,4,5,6,7,7,8,9}. 用JAVA怎么编写

我只能告诉你思路、你自己用语言去写好了、用两个指针head1,head2分别指向链表、同时扫描、因为合并为递增、时间复杂度为O（N）+O（N）=O（N），空间复杂度为O（N）

成都创新互联公司不只是一家网站建设的网络公司；我们对营销、技术、服务都有自己独特见解，公司采取“创意+综合+营销”一体化的方式为您提供更专业的服务！我们经历的每一步也许不一定是最完美的，但每一步都有值得深思的意义。我们珍视每一份信任，关注我们的网站设计制作、成都网站制作质量和服务品质，在得到用户满意的同时，也能得到同行业的专业认可，能够为行业创新发展助力。未来将继续专注于技术创新，服务升级，满足企业一站式网络营销推广需求，让再小的品牌网站建设也能产生价值！

if(head1-data=head2-data) head1接在head2前面，反之就在后面，具体代码你自己写吧。这个方法是增加了额外的空间。

如果不用额外的空间、那么直接原表上操作、但是会破坏原数据结构、

复制二叉树的非递归算法.算法思想和算法实现.

void Main()

{

BNode node = new BNode(){

value = "1",

lNode = new BNode(){

value = "1-1"

},

rNode = new BNode(){

value = "1-2",

lNode = new BNode() {

value = "1-2-1",

rNode = new BNode() {

value = "1-2-1-2"

}

},

rNode = new BNode() {

value = "1-2-2"

}

}

};

BNode clone = Clone(node); 

}

BNode Clone(BNode source) {

StackBNode stack = new StackBNode();

stack.Push(source);

BNode dest = new BNode();

StackBNode stackDest = new StackBNode();

stackDest.Push(dest);

while (stack.Count0) {

//复制节点的值

BNode s = stack.Peek();

BNode d = stackDest.Peek();

d.value = s.value;

if (s.lNode != null) { //寻找左子树 作为下一个结点

stack.Push(s.lNode);

d.lNode = new BNode();

stackDest.Push(d.lNode);

} else if (s.rNode != null) { //没有就找右子树

stack.Push(s.rNode);

d.rNode = new BNode();

stackDest.Push(d.rNode);

} else { //全没有 跳转到父结点的右子树

while (true) {

stack.Pop();

stackDest.Pop();

if (stack.Count = 0) break;

BNode p = stack.Peek();

if (p.rNode == s) { //已经使用过右结点 向上继续回溯

s = p;

}

else if (p.rNode != null) {

stack.Push(p.rNode);

d = stackDest.Peek();

d.rNode = new BNode();

stackDest.Push(d.rNode);

break;

} 

else s=p;

}

}

}

return dest;

}

// Define other methods and classes here

class BNode {

public object value;

public BNode lNode;

public BNode rNode;

}

算法思想的话就是构建两个栈用于回溯父结点...

其实递归算法隐藏了栈而已... 手动把这个栈构建出来就算成功了...

以上是一段C#代码示例   java代码应该复制粘贴就能用  C或者C++的话把BNode写成指针就可以使用...

java 判断链表是否有环

方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

例如这样的链表：A-B-C-D-B-C-D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。

假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 ， 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。

这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。

假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。

方法三：首先创建两个指针1和2（在java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。

例如链表A-B-C-D-B-C-D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。

此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

package demo6;import java.util.HashMap;import demo6.LinkReverse2.Node;/**

* 判断链表是否有环的方法

* @author mengfeiyang

*

*/public class LinkLoop {

public static boolean hasLoop(Node n){        //定义两个指针tmp1,tmp2

Node tmp1 = n;

Node tmp2 = n.next;        while(tmp2!=null){            int d1 = tmp1.val;            int d2 = tmp2.val;            if(d1 == d2)return true;//当两个指针重逢时，说明存在环，否则不存在。

tmp1 = tmp1.next;  //每次迭代时，指针1走一步，指针2走两步

tmp2 = tmp2.next.next;            if(tmp2 == null)return false;//不存在环时，退出

}        return true; //如果tmp2为null，说明元素只有一个，也可以说明是存在环

}    //方法2：将每次走过的节点保存到hash表中，如果节点在hash表中，则表示存在环

public static boolean hasLoop2(Node n){

Node temp1 = n;

HashMapNode,Node ns = new HashMapNode,Node();        while(n!=null){            if(ns.get(temp1)!=null)return true;            else ns.put(temp1, temp1);

temp1 = temp1.next;            if(temp1 == null)return false;

}        return true;

}    public static void main(String[] args) {

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

n1.next = n2;

n2.next = n3;

n3.next = n4;

n4.next = n5;

n5.next = n1;  //构造一个带环的链表,去除此句表示不带环

System.out.println(hasLoop(n1));

System.out.println(hasLoop2(n1));

}

}

执行结果：truetrue

java中关于LinkList的问题

//单链表类

package dataStructure.linearList;

import dataStructure.linearList.Node; //导入单链表结点类

import java.util.Iterator; //导入迭代器接口

public class SinglyLinkedListE extends AbstractListE implements LListE //单链表类，实现线性表接口

{

protected NodeE head; //头指针，指向单链表第1个结点

public SinglyLinkedList() //构造空单链表

{

this.head = null;

}

public SinglyLinkedList(NodeE head) //构造指定头指针的单链表

{

this.head = head;

}

public boolean isEmpty() //判断单链表是否为空，O(1)

{

return this.head==null;

}

public int length() //返回单链表长度

{ //单链表遍历算法，O(n)

int i=0;

NodeE p=this.head;

while (p!=null)

{

i++;

p = p.next;

}

return i;

}

public E get(int index) //返回序号为index的对象，index初值为0

{ //若单链表空或序号错误返回null，O(n)

if (this.head!=null index=0)

{

int j=0;

NodeE p=this.head;

while (p!=null jindex)

{

j++;

p = p.next;

}

if (p!=null)

return (E)p.data;

}

return null;

}

public E set(int index, E element) //设置序号为index的对象为element，O(n)

{ //若操作成功返回原对象，否则返回null

if (this.head!=null index=0 element!=null)

{

int j=0;

NodeE p=this.head;

while (p!=null jindex)

{

j++;

p = p.next;

}

if (p!=null)

{

E old = (E)p.data;

p.data = element;

return old; //若操作成功返回原对象

}

}

return null; //操作不成功

}

public boolean add(int index, E element) //插入element对象，插入后对象序号为index

{ //若操作成功返回true，O(n)

if (element==null)

return false; //不能添加空对象（null）

if (this.head==null || index=0) //头插入

this.head = new NodeE(element, this.head);

else //单链表不空且index=1

{

int j=0;

NodeE p=this.head;

while (p.next!=null jindex-1) //寻找插入位置

{

j++;

p = p.next;

}

p.next = new NodeE(element, p.next);//中间/尾插入

}

return true;

}

public boolean add(E element) //在单链表最后添加对象，重载，O(n)

{

return add(Integer.MAX_VALUE, element);

}

public E remove(int index) //移去序号为index的对象，O(n)

{ //若操作成功返回被移去对象，否则返回null

E old = null;

if (this.head!=null index=0)

if (index==0) //头删除

{

old = (E)this.head.data;

this.head = this.head.next;

}

else //中间/尾删除

{

int j=0;

NodeE p=this.head;

while (p.next!=null jindex-1) //定位到待删除结点的前驱结点

{

j++;

p = p.next;

}

if (p.next!=null)

{

old = (E)p.next.data; //操作成功，返回原对象

p.next = p.next.next; //删除p的后继结点

}

}

return old;

}

public void clear() //清空单链表，O(1)

{

this.head = null;

}

public String toString() //返回显示单链表所有元素值对应的字符串

{ //单链表遍历算法，O(n)

String str="(";

NodeE p = this.head;

while (p!=null)

{

str += p.data.toString();

p = p.next;

if (p!=null)

str += ", ";

}

return str+")";

}

//以上实现LList接口，第2章

//以下2.4 迭代器内容

public IteratorE iterator() //返回一个迭代器对象

{

return new Itr();

}

private class Itr implements IteratorE //私有内部类，实现迭代器接口

{

private NodeE cursor = head;

public boolean hasNext() //若有后继元素，返回true

{

return cursor!=null cursor.next!=null;

}

public E next() //返回后继元素

{

if (cursor != null cursor.next!=null)

{

E element = cursor.next.data;

cursor = cursor.next;

return element;

}

return null;

}

public void remove() //不支持该操作

{

throw new UnsupportedOperationException();

}

}//内部类Itr结束

//以下第8章 8.2.1 顺序查找，散列表中用

public NodeE search(E element, NodeE start) //从单链表结点start开始顺序查找指定对象

{ //若查找成功返回结点，否则返回null

if (this.head==null || element==null)

return null;

NodeE p=start;

while (p!=null !element.equals(p.data))

{

System.out.print(p.data+"? ");

p = p.next;

}

return p;

}

public NodeE search(E element) //顺序查找指定对象

{

return search(element, head);

}

/*

public boolean contain(E element) //以查找结果判断单链表是否包含指定对象

{ //若包含返回true，否则返回false

return this.search(element)!=null;

}

*/

public boolean remove(E element) //移去首次出现的指定对象，O(n)

{ //若操作成功返回true

if (this.head==null || element==null)

return false;

if (element.equals(this.head.data))

{

this.head = this.head.next; //头删除

return true;

}

NodeE front=this.head, p=front.next; //中间/尾删除

while (p!=null !element.equals(p.data))

{

front = p;

p=p.next;

}

if (p!=null)

{

front.next = p.next;

return true;

}

return false;

}

//以下是第2章习题

public SinglyLinkedList(E[] element) //由指定数组中的多个对象构造单链表

{

this.head = null;

if (element!=null element.length0)

{

this.head = new Node(element[0]);

NodeE rear=this.head;

int i=1;

while (ielement.length)

{

rear.next = new Node(element[i++]);

rear = rear.next;

}

}

}

public void concat(SinglyLinkedList list) //将指定单链表list链接在当前单链表之后

{

if (this.head==null)

this.head = list.head;

else

{

NodeE p=this.head;

while (p.next!=null)

p = p.next;

p.next = list.head;

}

}

public SinglyLinkedList(SinglyLinkedListE list) //以单链表list构造新的单链表

{ //复制单链表

this.head = null;

if (list!=null list.head!=null)

{

this.head = new Node(list.head.data);

NodeE p = list.head.next;

NodeE rear = this.head;

while (p!=null)

{

rear.next = new NodeE(p.data);

rear = rear.next;

p = p.next;

}

}

}

//递归方法

// public SinglyLinkedList(SinglyLinkedListE list) //以单链表list构造新的单链表

public void copy(SinglyLinkedListE list) //复制单链表

{

this.head = copy(list.head);

}

private NodeE copy(NodeE p) //复制单链表，递归方法

{

NodeE q=null;

if (p!=null)

{

q = new Node(p.data);

q.next = copy(p.next);

}

return q;

}

/*//递归方法

public String toString()

{

return "("+ this.toString(this.head) +")";

}

public String toString(NodeE p) //递归方法

{

if (p!=null)

return p.data.toString() + ", " + this.toString(p.next); //递归调用

return "";

}

public SinglyLinkedList(E[] element) //由指定数组中的多个对象构造单链表

{

this.head = null;

if (element!=null)

this.head = create(element,0);

}

private NodeE create(E[] element, int i) //由指定数组构造单链表

{ //递归方法

NodeE p=null;

if (ielement.length)

{

p = new Node(element[i]);

p.next = create(element, i+1);

}

return p;

}

*/

public boolean equals(Object obj) //比较两条单链表是否相等

{

if (obj == this)

return true;

if (obj instanceof SinglyLinkedList)

{

SinglyLinkedList list = (SinglyLinkedList)obj;

return equals(this.head, list.head);

}

return false;

}

private boolean equals(NodeE p, NodeE q) //比较两条单链表是否相等，递归方法

{

if (p==null q==null)

return true;

if (p!=null q!=null)

return p.data.equals(q.data) equals(p.next, q.next);

return false;

}

//以下是第8章习题

public boolean replace(Object obj, E element)//将元素值为obj的结点值替换为element，O(n)

{ //若替换成功返回true，否则返回false

if (obj==null || element==null)

return false;

NodeE p=this.head;

while (p!=null)

{

if (obj.equals(p.data))

{

p.data = element;

return true;

}

p = p.next;

}

return false;

}

public boolean replaceAll(Object obj, E element) //将所有元素值为obj的结点值替换为element，O(n)

{ //若替换成功返回true，否则返回false

boolean done=false;

if (obj!=null element!=null)

{

NodeE p=this.head;

while (p!=null)

{

if (obj.equals(p.data))

{

p.data = element;

done = true;

}

p = p.next;

}

}

return done;

}

public boolean removeAll(Object obj) //将所有元素值为obj的结点删除

{

if (this.head==null || obj==null)

return false;

boolean done=false;

while (this.head!=null obj.equals(this.head.data))

{

this.head = this.head.next; //头删除

done = true;

}

NodeE front=this.head, p=front.next;

while(p!=null)

{

if (obj.equals(p.data))

{

front.next = p.next; //删除p结点

p = front.next;

done = true;

}

else

{

front = p;

p = p.next;

}

}

return done;

}

public static void main(String[] args)

{

String[] letters={"A","B","C","D","E","F"};

SinglyLinkedListString list1 = new SinglyLinkedListString(letters);

SinglyLinkedListString list2 = new SinglyLinkedListString(list1);

list2.copy(list1);

System.out.println(list2.toString());

System.out.println("equals()， "+list2.equals(list1));

}

}

/*

程序运行结果如下：

(A, B, C, D, E, F)

*/

/* 第2章 //可行，但效率低，时间复杂度是O(n*n)。

public String toString()

{

String str="{";

if (this.length()!=0)

{

for(int i=0; ithis.length()-1; i++)

str += this.get(i).toString()+", ";

str += this.get(this.length()-1).toString();

}

return str+"}";

}

*/