写点什么

找到相同链表的点

用户头像
落朽
关注
发布于: 2020 年 12 月 12 日


import java.util.Set;import java.util.Stack;
public class SimpleLink { //头结点 public Node header;
//尾结点 public Node tail; //链表长度默认为零 private int length = 0;
public SimpleLink insert(String data) { Node node = new Node(data); if (header == null) { tail = node; header = node; }else{ tail.next=node; tail = node; } length++; return this; }

public void reserver(Node node){
if(node == header){ tail = header; } header = node; if(node.next==null){ return; } Node pre = node.next; reserver(pre); pre.next = node;
}

public void print(){ Node node = header; if(header==null){ System.out.println("empty"); } while (node!=null){ System.out.print("--->"+node.getData()); if(node!=tail){ node = node.next; }else{ break; }
} System.out.println(); }
public int getLength(){ return length; }

public static void main(String[] args){ //存储链表 a-->b-->x-->y--->z SimpleLink simpleLink1 = new SimpleLink(); simpleLink1.insert("a").insert("b").insert("x").insert("y").insert("z"); simpleLink1.print(); //存储链表 d-->e--f-->x-->y--->z SimpleLink simpleLink2 = new SimpleLink(); simpleLink2.insert("d").insert("e").insert("f").insert("x").insert("y").insert("z"); simpleLink2.print(); //linkForeach(simpleLink1, simpleLink2); //stackForeach(simpleLink1, simpleLink2); reserverLink(simpleLink1, simpleLink2); }
/** * 反转链表,节省空间 * @author liuxiaokun * @date Created in 2020/12/10 3:13 PM * @param simpleLink1  * @param simpleLink2 * @return void */ private static void reserverLink(SimpleLink simpleLink1, SimpleLink simpleLink2) { simpleLink1.reserver(simpleLink1.header); simpleLink2.reserver(simpleLink2.header); Node header1 = simpleLink1.header; Node header2 = simpleLink2.header; String start = null; while( header1!=null || header2!=null){ if(header1.getData().equals(header2.getData())){ start = header1.getData(); header1 = header1.next; header2 = header2.next; }else{ break; } } System.out.println("start......."+start); }
/** * 用栈的特性来解决,最后相当于把链表逆转,最后的在上面,然后一个个取,最后一个相同的就是链表相同的第一个 * @author liuxiaokun * @date Created in 2020/12/10 2:58 PM * @param simpleLink1  * @param simpleLink2 * @return void */ private static void stackForeach(SimpleLink simpleLink1, SimpleLink simpleLink2) { Stack<String> stack1 = new Stack<String>(); Node header1 = simpleLink1.header; while(header1!=null){ stack1.push(header1.getData()); if(header1!=simpleLink1.tail){ header1 = header1.next; }else { break; } }
Stack<String> stack2 = new Stack<String>(); Node header2 = simpleLink2.header; while(header2!=null){ stack2.push(header2.getData()); if(header2!=simpleLink2.tail){ header2 = header2.next; }else { break; } } String start =null; while ((!stack1.empty()) || (!stack2.empty())){ String str1 = stack1.pop(); String str2 = stack2.pop(); if(str1.equals(str2)){ start = str1; }else { break; } } System.out.println("start......."+start); }
/** * 利用循环操作,时间复杂度O(n),空间复杂度O(n) * @author liuxiaokun * @date Created in 2020/12/10 2:41 PM * @param simpleLink1  * @param simpleLink2 * @return void */ private static void linkForeach(SimpleLink simpleLink1, SimpleLink simpleLink2) { //获取最小长度 int len1 = simpleLink1.getLength(); int len2 = simpleLink2.getLength(); int maxLen = Math.max(len1,len2); SimpleLink minLink = simpleLink1; SimpleLink maxLink = simpleLink2; int minLen = len1; if(maxLen == len1){ minLink = simpleLink2; maxLink = simpleLink1; minLen = len2; } Set<String> set = new java.util.HashSet<>(minLen); Node header1 = minLink.header; while(header1!=null){ set.add(header1.getData()); if(header1!=minLink.tail){ header1 = header1.next; }else { break; } }
Node header2 = maxLink.header; while(header2!=null){ String str = header2.getData(); if(set.contains(str)){ System.out.println("start......."+str); return; } if(header2!=maxLink.tail){ header2 = header2.next; }else { break; } } }}
class Node {
public Node next; private String data;
public Node(String data) { this.data = data; this.next = null; }

public String getData() { return data; }
@Override public String toString(){ return this.data; }}
复制代码

分析:

linkForeach 的方法。时间为小链表 o(n)+大链表 o(n)。其实有一个 set 的 contains 方法,这个方法因为用的 hashset,所以查找很快,可以忽略不计。时间复杂度 O(n)。需要申请一个空间,长度等于小链表的长度。

stackForeach 方法:时间为为小链表 o(n)+大链表 o(n)+相同的长度 o(n),所以时间复杂度 O(n)。需要申请两个栈的空间,空间大小和链表大小相同,这样就是好理解。相当于反转链表,比如例子:第一个链表(a-->b-->x-->y--->z)反转后(z-->y-->x-->b--->a),第二个链表(d-->e--f-->x-->y--->z)返回后(z-->y-->x-->f--->e--->d),这样就更容易比较理解。空间复杂度也是 O(n)

reserverLink 方法:反转链表用的时间复杂度 n*log(n),时间变得长了,但是时间复杂度还是 O(n),不过不需要另外的空间,节省了空间。道理和 stackForeach 方法类似


用户头像

落朽

关注

还未添加个人签名 2018.03.26 加入

还未添加个人简介

评论

发布
暂无评论
找到相同链表的点