本文共 6553 字，大约阅读时间需要 21 分钟。

两个链表的合成

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

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

两个链表的公共节点

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

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;    }}