找到相同链表的点
发布于: 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 方法类似
划线
评论
复制
发布于: 2020 年 12 月 12 日阅读数: 27
落朽
关注
还未添加个人签名 2018.03.26 加入
还未添加个人简介
评论