目录

单选链表的基本实现

有序列表的合并（双指针法）

链表的反转 

链表实现两数之和 

判定链表是否有环

---

双链表的实现

public class DLinkedList<E> {private Node<E> first;private Node<E> last;int size;/*** 头插法* @param item*/public void addFirst(E item){Node<E> f =first;Node<E> newNode =new Node<E>(null,item,f);first =newNode;if (f==null){last =newNode;}else {f.prev=newNode;}size++;}/*** 尾插法* @param item*/public void addLast(E item){Node<E> l =last;Node<E> newNode =new Node<E>(l,item,null);last =newNode;if (l==null){first=newNode;}else {l.next=newNode;}size++;}/*** 删除头节点*/public void deleteFirst(){Node<E> f =first;Node<E> n =first.next;f.next =null;f.item=null;first=n;if (n==null){last=null;}else {n.prev=null;}size--;}/*** 删除尾节点*/public void deleteLast(){Node<E> l =last;Node<E> p =last.prev;l.item=null;l.prev=null;last=p;if (p==null){first=null;}else {p.next=null;}size--;}/*** 从头开始遍历* @return*/public String toStringForFirst() {StringJoiner sj =new StringJoiner("->");for (Node<E> n= first;n!=null;n =n.next){sj.add(n.item.toString());}return sj.toString();}/*** 从尾开始遍历* @return*/public String toStringForLast(){StringJoiner sj =new StringJoiner("<-");for (Node<E> n =last;n!=null;n=n.prev){sj.add(n.item.toString());}return sj.toString();}@Overridepublic String toString() {StringJoiner sj =new StringJoiner("<->");for (Node<E> n= first;n!=null;n =n.next){sj.add(n.item.toString());}return sj.toString();}/*** 节点内部类* @param <E>*/static class Node<E>{private E item;private Node<E> prev;private Node<E> next;Node(Node<E> prev,E item,Node<E> next){this.prev=prev;this.item=item;this.next=next;}}
}

单链表的实现

public class LinkedList1 {//头节点Node first;//尾节点Node last;//大小int size = 0;//头插法public void addFirst(int v) {Node newNode = new Node(v);Node f = first;first = newNode;if (f == null) {last = newNode;} else {newNode.next = f;}size++;}//尾插法public void addLast(int v) {Node newNode = new Node(v);Node l = last;last = newNode;if (l == null) {first = newNode;} else {l.next = newNode;}size++;}//使用节点尾插public void addNode(Node node){if (last ==null){last=node;first=node;}else {Node l =last;l.next=node;last=node;}}//链表的遍历@Overridepublic String toString() {StringJoiner sj = new StringJoiner("->");for (Node n = first; n != null; n = n.next) {sj.add(String.valueOf(n.val));}return sj.toString();}public static class Node {int val;Node next;Node(int val) {this.val = val;}}
}

有序列表的合并（双指针法）

//链表的有序合并排序public static LinkedList1 merge(LinkedList1 list1, LinkedList1 list2) {Node n1 = list1.first, n2 = list2.first;LinkedList1 result = new LinkedList1();while (n1 != null || n2 != null) {if (n1 == null) {result.addLast(n2.val);n2 = n2.next;continue;}if (n2 == null) {result.addLast(n1.val);n1 = n1.next;continue;}if (n1.val < n2.val) {result.addLast(n1.val);n1 = n1.next;} else {result.addLast(n2.val);n2 = n2.next;}}return result;}

 测试

LinkedList1 linkedList1 =new LinkedList1();linkedList1.addLast(1);linkedList1.addLast(4);linkedList1.addLast(6);LinkedList1 linkedList2 =new LinkedList1();linkedList2.addLast(2);linkedList2.addLast(3);linkedList2.addLast(5);linkedList2.addLast(9);System.out.println("链表1："+linkedList1);System.out.println("链表2："+linkedList2);//有序链表的合并排序System.out.println("链表1与链表2合并："+LinkedList1.merge(linkedList1, linkedList2));

链表的反转 

//链表的反转public static LinkedList1 reverseLinked(LinkedList1 list1) {Stack<Node> stack = new Stack<>();for (Node n = list1.first; n != null; n = n.next) {stack.add(n);}LinkedList1 result = new LinkedList1();while (!stack.isEmpty()) {result.addLast(stack.pop().val);}return result;}

测试

        LinkedList1 linkedList1 =new LinkedList1();linkedList1.addLast(1);linkedList1.addLast(4);linkedList1.addLast(6);System.out.println("链表1："+linkedList1);//链表的反转System.out.println("链表1反转后："+LinkedList1.reverseLinked(linkedList1));

测试结果

链表实现两数之和 

    //两数之和public static LinkedList1 addNumber(LinkedList1 list1, LinkedList1 list2) {Node n1 = list1.first, n2 = list2.first;LinkedList1 result = new LinkedList1();int carry = 0;while (n1 != null || n2 != null) {int x = n1 != null ? n1.val : 0;int y = n2 != null ? n2.val : 0;int sum = x + y + carry;carry = sum / 10;result.addLast(sum % 10);if (n1 != null) {n1 = n1.next;}if (n2 != null) {n2 = n2.next;}}if (carry != 0) {result.addLast(carry);}return result;}

测试

        LinkedList1 linkedList1 =new LinkedList1();linkedList1.addLast(1);linkedList1.addLast(4);linkedList1.addLast(6);LinkedList1 linkedList2 =new LinkedList1();linkedList2.addLast(2);linkedList2.addLast(3);linkedList2.addLast(5);linkedList2.addLast(9);//两数之和System.out.println("链表1："+linkedList1);System.out.println("链表2："+linkedList2);System.out.println("链表1+链表2："+LinkedList1.addNumber(linkedList1,linkedList2));

测试结果（注意从左到右依次是个十百位）

判定链表是否有环

方法一 通过set集合

    //set集合判断是否有环public static boolean hasCycle(Node node) {Set<Node> set = new HashSet<>();while (node != null) {if (set.contains(node)) {return true;}set.add(node);node = node.next;}return false;}

方法二 通过快慢指针

    //快慢指针判断是否有环public static boolean hasCycle2(Node node) {Node fast = node;//快指针Node slow = node;//慢指针//判断是不是空节点if (node == null) {return false;}while (fast != null && fast.next != null && slow != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}

测试 无论方法一还是二 测试结果都是相同 一般使用方法二 效率更高 更节省资源

        LinkedList1.Node node1 =new LinkedList1.Node(1);LinkedList1.Node node2 =new LinkedList1.Node(2);LinkedList1.Node node3 =new LinkedList1.Node(3);LinkedList1.Node node4 =new LinkedList1.Node(4);LinkedList1.Node node5 =new LinkedList1.Node(5);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;node5.next=node3;//环 注意这是专门设置的环//set集合判断是否有环System.out.println("set集合判断是否有环:"+LinkedList1.hasCycle(node1));//快慢指针判断是否有环System.out.println("快慢指针判断是否有环:"+LinkedList1.hasCycle2(node1));

测试结果