壁纸公司网站源码,大型购物网站排名,香烟网上商城,寮步网站建设价钱文章目录 以给定值x为基准将链表分割成两部分#xff0c;所有小于x的结点排在大于或等于x的结点之前输入两个链表#xff0c;找出它们的第一个公共结点。给定一个链表#xff0c;判断链表中是否有环无头双向链表的模拟实现ArrayList#xff08;顺序表#xff09;和LinkedL… 文章目录 以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前输入两个链表找出它们的第一个公共结点。给定一个链表判断链表中是否有环无头双向链表的模拟实现ArrayList顺序表和LinkedList双向链表的区别总结 以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 public class Partition {public ListNode partition(ListNode pHead, int x) {// write code here//创建四个节点ListNode bs null;ListNode be null;ListNode as null;ListNode ae null;ListNode cur pHead; if(cur null){return null;}while(cur ! null){if(cur.val x){//小于x放左边if(bs null){//当bs里面没有节点时bs cur;be cur; }else{//有节点了用be去遍历be.next cur;be cur;}}else{//大于x放右边if(as null){//当as里面没有节点时as cur;ae cur;}else{//有节点了用ae去遍历ae.next cur;ae cur;}}cur cur.next;}//cur遍历完了开始串起来//如果前面为空if(bs null){return as;}//如果都不为空be.next as;//如果后面不为空要置为空if(as ! null){ae.next null;}return bs;
}
}输入两个链表找出它们的第一个公共结点。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB){ListNode cur1 headA;ListNode cur2 headB; int len1 0;int len2 0;//1.求链表的长度while(cur1 ! null){len1;//5cur1 cur1.next;}while(cur2 ! null){len2;//2cur2 cur2.next;}cur1 headA;cur2 headB; //int len math.abs(len1 - len2);//3//2.走差值步if(len1len2){for(int i 0;i len1-len2;i){cur1 cur1.next;}}else{for(int j 0;j len2 - len1;j){cur2 cur2.next;}}//3.同时走while(cur1 ! cur2 ){cur1 cur1.next;cur2 cur2.next;}//如果没相遇都是空if(cur1 null){return null;}return cur1;}
}给定一个链表判断链表中是否有环 public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){fast fast.next.next;//走两步slow slow.next;//走一步if(fast slow){return true;}}return false;}}无头双向链表的模拟实现
public interface IList {// 2、无头双向链表实现//头插法void addFirst(int data);void addLast(int data);//任意位置插入,第一个数据节点为0号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();void display();void clear();
}public class MyLinkedList implements IList {//节点内部类static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val val;}}public ListNode head;public ListNode last;Overridepublic void addFirst(int data) {//实例化一个节点ListNode node new ListNode(data);if (head null){head node;last node;}else{node.next head;head.prev node;head node;}}//尾插法Overridepublic void addLast(int data) {ListNode node new ListNode(data);if (last null){last node;head node;}else{last.next node;node.prev last;last node;}}//让cur去到index位置private ListNode findIndex(int index){ListNode cur this.head;//index-1while(index ! 0){cur cur.next;index--;}return cur;}// 插入节点Overridepublic void addIndex(int index, int data) {ListNode node new ListNode(data);//检查index是否合法if(index 0 || index size()){//抛出自定义异常System.out.println(index不合法);return;}//头插法if(index 0){
// node.next head;
// head.prev node;
// head node;addFirst(data);return;}//尾插法if (index size()){
// last.next node;
// node.prev last;
// last node;addLast(data);return;}ListNode cur findIndex(index);node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;}Overridepublic boolean contains(int key) {ListNode cur head;while(cur ! null){if (cur.val key){return true;}cur cur.next;}return false;}Overridepublic void remove(int key) {ListNode cur head;while (cur ! null) {//如果等于关键字进入循环if (cur.val key) {//删除头if (cur head) {//如果只有一个节点head head.next;//head已经删了if (head ! null){//如果有很多节点head.prev null;}last null;} else {//删中间节点和尾巴节点的共同代码cur.prev.next cur.next;if (cur.next null) {//删尾巴节点last last.prev;} else {//删中间节点cur.next.prev cur.prev;}}return;}else{//不等于cur往后走cur cur.next;}}}Overridepublic void removeAllKey(int key) {ListNode cur head;while (cur ! null) {//如果等于关键字进入循环if (cur.val key) {//删除头if (cur head) {//如果只有一个节点head head.next;//head已经删了if (head ! null){//如果有很多节点head.prev null;}last null;} else {//删中间节点和尾巴节点的共同代码cur.prev.next cur.next;if (cur.next null) {//删尾巴节点last last.prev;} else {//删中间节点cur.next.prev cur.prev;}}}//继续往后遍历cur cur.next;}}//求链表长度Overridepublic int size() {ListNode cur head;int count 0;while(cur ! null){count;cur cur.next;}return count;}//打印链表Overridepublic void display() {ListNode cur head;while(cur ! null){System.out.print(cur.val );cur cur.next;}System.out.println();}Overridepublic void clear() {head null;last null;}
}public class TestLink {//遍历链表public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(3);list.add(5);list.add(7);list.add(9);list.add(12);System.out.println(list);System.out.println();for (int i 0; i list.size(); i) {System.out.print(list.get(i) );}}
}ArrayList顺序表和LinkedList双向链表的区别 总结
链表的学习就到这里最重要的就是什么是链表链表又细分为哪些链表要会把链表画出来链表和顺序表的区别链表的各种方法的实现链表的各种练习题等。
