Week 08 命题作业

import java.util.ArrayList;import java.util.List;
public class Test2 {	public static void main(String[] args) {				// 链表1数据初始化		MyLinkedList<String> list1 = new MyLinkedList<String>();		list1.addLast("a");		list1.addLast("b");		list1.addLast("x");		list1.addLast("y");		list1.addLast("z");				int m = list1.size();//链表1的长度						// 链表2数据初始化		MyLinkedList<String> list2 = new MyLinkedList<String>();		list2.addLast("d");		list2.addLast("e");		list2.addLast("f");		list2.addLast("x");		list2.addLast("y");		list2.addLast("z");				int n = list2.size();//链表2的长度						// 如果仅仅是判断两条链表是否相交，最简单的方法是判断两个链表的最后一个结点是否相等，如果相等，那么这两个链表就相交：		// 此判断的时间复杂度为O(m+n)		System.out.println("判断两个链表是否相交[时间复杂度O(m+n)="+(m+n)+"]："+(list1.get(list1.size()-1).equals(list2.get(list2.size()-1))));				// 找出相交元素方法一：		// 如果要求出哪些元素相交，可从任意一个链表进行遍历，然后每次遍历时判断第二个链表中是否包含了该元素：		// 此时时间复杂度为O(m*n)		int o1=0;		List<String> resultList = new ArrayList<String>();		for(int i=0;i<list1.size();i++){			String tmp1 = list1.get(i);			for(int j=0;j<list2.size();j++){				String tmp2 = list2.get(j);				if(tmp1.equals(tmp2)){					resultList.add(tmp1);				}				o1++;			}		}				System.out.println("以下是两个链表相交的元素[时间复杂度O(m*n)="+o1+"]：");				for(String temp : resultList){			System.out.println(temp);		}			/*			判断两个链表是否相交[时间复杂度O(m+n)=11]：true			以下是两个链表相交的元素[时间复杂度O(m*n)=30]：			x			y			z		*/	}}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////下面是自定义单链表相关类///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


//单链表节点类class Node<E> {	    // 元素值	    E data;	    // 当前节点的下一节点的引用	    Node<E> next;
	    Node(E element) {	        this.data = element;	    }	    	    Node(E element, Node<E> next) {	        this.data = element;	        this.next = next;	    }}
// 单链表类class MyLinkedList<E>{		int size = 0; // 记录链表的大小	Node<E> head; // 表示链表的头节点		// 在链表头添加节点    public void addHead(E data){        Node<E> node = new Node<E>(data);        if(size==0){            head = node;        }else{        	node.next = head;            head = node;        }        size++;    }        // 往链表末尾加入节点    public void addLast(E data) {		// 实例化一个节点		Node<E> newNode = new Node<E>(data);		// 判断头节点是否为空,如果是空就给他赋值		if (head == null) {			head = newNode;		}else{			// 接收head头指针的对象			Node<E> temp = head;			// 遍历单链表,直到遍历到最后一个则跳出循环。			while (temp.next != null) {				// 往后移动一个节点,指向下一个节点				temp = temp.next;			}			// temp为最后一个节点或者是头节点,将其next指向新节点			temp.next = newNode;		}		size++;	}        // 删除指定下标的节点    public boolean delete(int index) {        if (index < 0 || index >= size()) {            return false;        }        if (index == 0) {            head = head.next;            return true;        }        int i = 1;        Node<E> preNode = head;        Node<E> curNode = preNode.next;        while (curNode != null) {            if (i == index) {                preNode.next = curNode.next;                return true;            }            preNode = curNode;            curNode = curNode.next;            i++;        }        return false;    }	    // 获取链表大小	public int size(){		return size;	}		// 根据下标获取节点值	public E get(int index){		if(index >= 0 && index < size()){			int i = 0;			Node<E> tmp = head;			while (tmp != null) {				if(i == index){					return tmp.data;				}				tmp = tmp.next;				i++;			}		}		return null;	}		// 根据下标获取节点对象	public Node<E> getNode(int index){		if(index >= 0 && index < size()){			int i = 0;			Node<E> tmp = head;			while (tmp != null) {				if(i == index){					return tmp;				}				tmp = tmp.next;				i++;			}		}		return null;	}
		// 打印单链表	public void printList() {		Node<E> tmp = head;		while (tmp != null) {			System.out.println(tmp.data);			tmp = tmp.next;		}	}}

判断两个链表是否相交[时间复杂度O(m+n)=11]：true			以下是两个链表相交的元素[时间复杂度O(m*n)=30]：			x			y			z