哪家公司做企业网站稳定优惠,网站备案信息注销,ios注册开发者账号,vue 企业网站模板目录
单选链表的基本实现
有序列表的合并#xff08;双指针法#xff09;
链表的反转
链表实现两数之和
判定链表是否有环 单选链表的基本实现
public class LinkedList1 {//头节点Node first;//尾节点Node last;//大小int size 0;//头插法public void addFirst(int…目录
单选链表的基本实现
有序列表的合并双指针法
链表的反转
链表实现两数之和
判定链表是否有环 单选链表的基本实现
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){lastnode;firstnode;}else {Node l last;l.nextnode;lastnode;}}//链表的遍历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(链表1linkedList1);System.out.println(链表2linkedList2);//有序链表的合并排序System.out.println(链表1与链表2合并LinkedList1.merge(linkedList1, linkedList2)); 链表的反转
//链表的反转public static LinkedList1 reverseLinked(LinkedList1 list1) {StackNode 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(链表1linkedList1);//链表的反转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(链表1linkedList1);System.out.println(链表2linkedList2);System.out.println(链表1链表2LinkedList1.addNumber(linkedList1,linkedList2));
测试结果注意从左到右依次是个十百位 判定链表是否有环
方法一 通过set集合 //set集合判断是否有环public static boolean hasCycle(Node node) {SetNode 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.nextnode2;node2.nextnode3;node3.nextnode4;node4.nextnode5;node5.nextnode3;//环 注意这是专门设置的环//set集合判断是否有环System.out.println(set集合判断是否有环:LinkedList1.hasCycle(node1));//快慢指针判断是否有环System.out.println(快慢指针判断是否有环:LinkedList1.hasCycle2(node1));
测试结果
