13518219792
我只能告诉你思路、你自己用语言去写好了、用两个指针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写成指针就可以使用...
方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点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
//单链表类
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+"}";
}
*/
