JAVA初窥-DAY13

两个链表的合成

两个有序链表合成为一个有序链表：

public static MyList addList(MyList list1,MyList list2){
    Node f =new Node(-1);
    Node e =f;
    if (list1==null&&list2==null){
        return null;
    }
    for (;list1.head!=null && list2.head!=null;){
        if (list1.head.val<list2.head.val){
            e.next = list1.head;
            e = list1.head;
            list1.head = list1.head.next;
        }else {
            e.next = list2.head;
            e = list2.head;
            list2.head=list2.head.next;
        }
    }
    if (list1.head==null){
        e.next = list2.head;
    }else {
        e.next = list1.head;
    }
    list1.head = f.next;
    return list1;
}

两个链表的公共节点

寻找两个链表的公共节点：
main函数

	MyList list1 = new MyList();//链表1
	MyList list2 = new MyList();//链表2
	list1.addHead(11);
	list2.addHead(22);
	Node node = new Node(999);//创建公共节点
	list1.lastNode().next=node;//得到list1的最后一个节点并让其next等于node
	list2.lastNode().next=node;//得到list2的最后一个节点并让其next等于node
	list1.addHead(11);
	list1.addHead(11);
	list1.addLast(888);//公共部分
	list1.addLast(777);//公共部分
	list1.addLast(666);//公共部分
	list1.show();
	list2.show();
	System.out.println(MyList.publicNode(list1, list2).val);//输出公共节点的val值

相关方法函数

	public static Node publicNode(MyList list1,MyList list2){
	    Node node = new Node(-1);
	    Node cur1 = list1.head;
	    Node cur2 = list2.head;
	    int i;
	    for (;cur1.next!=null && cur2.next!=null;){
	        cur1 = cur1.next;
	        cur2 = cur2.next;
	    }
	    if(cur1.next == null){
	        for (i=0;cur2.next != null;i++){
	            cur2=cur2.next;
	        }
	        cur1=list1.head;
	        cur2=list2.head;
	        for (;i>0;i--){
	            cur2 = cur2.next;
	        }
	        for (;cur1 !=cur2;){
	            cur1 = cur1.next;
	            cur2 = cur2.next;
	        }
	    }else {
	        for (i=0;cur1.next != null;i++){
	            cur1=cur1.next;
	        }
	        cur1=list1.head;
	        cur2=list2.head;
	        for (;i>0;i--){
	            cur1 = cur1.next;
	        }
	        for (;cur1 !=cur2;){
	            cur1 = cur1.next;
	            cur2 = cur2.next;
	        }
	    }
	    if (cur1 != cur2){
	        System.out.println("没有公共节点");
	        return node;
	    }
	    return cur1;
	}
	
	
	public Node lastNode(){
	    Node cur = this.head;
	    for (;cur.next != null;){
	        cur = cur.next;
	    }
	    return cur;
	}

无头双向不循环链表的实现

main函数

public class Demo013 {
    public static void main(String[] args) {
        List list = new List();
        list.addFirst(3);
        list.addFirst(2);
        list.show();
        list.addLast(4);
        list.addFirst(1);
        list.show();
        list.addIndex(4,99);
        list.addIndex(0,99);
        list.addIndex(3,99);
        list.show();
        System.out.println(list.listSize);
        System.out.println("----------1----------");
        list.contains(1);
        list.remove(1);
        list.show();
        System.out.println("----------2----------");
        list.removeAllKey(99);
        list.show();
        System.out.println("----------3----------");
        list.clear();
        list.addLast(1);
        list.show();
    }
}

节点及链表及功能

public class List {

    public Node head;//头
    public Node tail;//尾巴
    public int listSize=0;

    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else {
            this.head.prev = node;
            node.next =head;
            this.head = this.head.prev;
        }
        listSize++;
    }
    //尾插法
    public void addLast(int data) {
        Node node = new Node(data);
        if (this.tail == null){
            this.tail = node;
            this.head = node;
        }else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = this.tail.next;
        }
        listSize++;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        Node node = new Node(data);
        Node cur = this.head;
        if (index<0||index>listSize){
            System.out.println("位置不合法！！");
            return;
        }
        if (index == 0){
            this.head.prev = node;
            node.next =head;
            this.head = this.head.prev;
            listSize++;
            return;
        }else if (index == listSize){
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = this.tail.next;
            listSize++;
            return;
        }else {
            for (; index != 0 ; ) {
                cur = cur.next;
                index--;
            }
            cur.prev.next = node;
            node.prev = cur.prev;
            node.next = cur;
            cur.prev = node;
            listSize++;
        }
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = this.head;
        for (;cur!=null;){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        Node cur = this.head.next;
        for (;cur!=this.tail;){
            if (cur.val == key){
                cur.next.prev = cur.prev;
                cur.prev.next = cur.next;
                listSize--;
                return;
            }
            cur = cur.next;
        }
        if (this.head.val == key){
            this.head = this.head.next;
            this.head.prev =null;
            listSize--;
            return;
        }else if (this.tail.val == key){
            this.tail = this.tail.prev;
            this.tail.next =null;
            listSize--;
            return;
        }
        System.out.println("未找到要删除的节点，请重新确认！");
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        Node cur = this.head.next;
        int tmpSize = listSize;
        for (;cur!=this.tail;){
            if (cur.val == key){
                cur.next.prev = cur.prev;
                cur.prev.next = cur.next;
                listSize--;
            }
            cur = cur.next;
        }
        if (this.head.val == key){
            this.head = this.head.next;
            this.head.prev=null;
            listSize--;
        }
        if (this.tail.val == key){
            this.tail = this.tail.prev;
            this.tail.next = null;
            listSize--;
        }
        if (tmpSize == listSize){
            System.out.println("未找到要删除的节点，请重新确认！");
        }else {
        System.out.println("删除成功！");
        }
    }

    public void show(){
        Node cur = this.head;
        for (;cur != null;){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void clear(){
        this.head = null;
        this.tail = null;
        listSize = 0;
    }

}

class Node {
    public int val;
    public Node prev;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}