有阿里云服务器 怎么做网站,大宗商品现货交易平台软件,中国建设企业银行网站首页,如何做阿里巴巴免费网站无头单向非循环链表实现 1. 单链表的模拟实现IList.java接口#xff1a;MySingleList.java文件#xff1a; 2. leetcode刷题2.1 获取链表的中间节点2.2 删除链表中所有值为value的元素2.3 单链表的逆置2.4 获取链表倒数第k个节点2.5 给定 x, 把一个链表整理成前半部分小于 x,… 无头单向非循环链表实现 1. 单链表的模拟实现IList.java接口MySingleList.java文件 2. leetcode刷题2.1 获取链表的中间节点2.2 删除链表中所有值为value的元素2.3 单链表的逆置2.4 获取链表倒数第k个节点2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式2.6 判定链表是否是回文2.7 判定链表相交并求出交点2.8 判断链表带环2.9 求环的入口点2.10 合并两个有序链表 写在最前面学习数据结构一定要结合画图先画图分析写出伪代码再仔细分析伪代码是否成立成立再写入题目中检验 1. 单链表的模拟实现
单链表的模拟实现需要创建三个文件IList.java接口文件MySingleList.java文件还有一个test.java测试文件。测试文件这里就不演示了。
IList.java接口
public interface IList {// 1、无头单向非循环链表实现//头插法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 clear();void display();
}MySingleList.java文件
public class MySingleList implements IList{static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;public void creatList() {ListNode node1 new ListNode(0);ListNode node2 new ListNode(1);ListNode node3 new ListNode(2);ListNode node4 new ListNode(3);node1.next node2;node2.next node3;node3.next node4;head node1;}Overridepublic void display() {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}Overridepublic void addFirst(int data) {ListNode node new ListNode(data);node.next head;head node;}Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(head null) {head node;return;}//找尾ListNode cur head;while(cur.next ! null) {cur cur.next;}cur.next node;}Overridepublic void addIndex(int index, int data) {if(index 0 || index size()) {System.out.println(index位置不合法);return;}if(index 0) {addFirst(data);return;}if(index size()){addLast(data);return;}ListNode node new ListNode(data);ListNode cur head;for (int i 0; i index-1; i) {cur cur.next;}node.next cur.next;cur.next 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) {if(head null) {return;}if(head.val key) {head head.next;return;}ListNode pre head;while(pre.next ! null) {if(pre.next.val key) {ListNode del pre.next;pre.next del.next;return;}pre pre.next;}}Overridepublic void removeAllKey(int key) {if(head null) {return;}ListNode pre head;ListNode cur head.next;while(cur ! null) {if(cur.val key) {pre.next cur.next;}else {pre cur;}cur cur.next;}//该if语句只能放在最后面如果头节点需要删除//删除后有可能下一个节点此时这个节点做头节点依然是需要删除的//因此只能放在最后当后面的都删除好了再检查头节点是否需要删除if(head.val key) {head head.next;}}Overridepublic int size() {int len 0;ListNode cur head;while(cur ! null) {cur cur.next;len;}return len;}Overridepublic void clear() {head null;}
}2. leetcode刷题
2.1 获取链表的中间节点
题目链接876. 链表的中间结点
注意题目中说明当链表只有一个中间结点时返回该节点而当该链表有两个中间结点返回第二个结点
解析定义一对“快慢指针”“快指针”为fast一次走两步“慢指针”为slow一次走一步。
当链表的结点个数为奇数个时fast走到fast.next null时slow此时所在位置就是中间节点当链表的节点个数为偶数个时fast走到fast null时slow此时所在位置就是中间节点
代码如下
class Solution {public ListNode middleNode(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}2.2 删除链表中所有值为value的元素
题目链接203. 移除链表元素
这题的题解和模拟实现单链表的removeAllKey是一样的故不再赘述。
代码如下
class Solution {public ListNode removeElements(ListNode head, int val) {if(head null) {return head;}ListNode pre head;ListNode cur head.next;while(cur ! null) {if(cur.val val) {pre.next cur.next;}else {pre cur;}cur cur.next;}if(head.val val) {head head.next;}return head;}
}2.3 单链表的逆置
题目链接206. 反转链表
解析只需将链表的每个箭头调转方向即可即修改当前节点的next值为前一个节点的地址修改后就无法获取下一个节点了故需要一个curN来定位下一个节点又由于是单链表无法得到前一个节点的位置所以还需要定义一个prev来定位前一个节点的位置 代码如下
class Solution {public ListNode reverseList(ListNode head) {if(head null || head.next null) {return head;}ListNode pre head;ListNode cur head.next;ListNode curN head.next.next;pre.next null;while(cur ! null) {cur.next pre;pre cur;cur curN;if(curN ! null) {curN curN.next;}}return pre;}
}2.4 获取链表倒数第k个节点
题目链接面试题 02.02. 返回倒数第 k 个节点
解析定义一对“快慢指针””快指针“fast先走k步然后”快指针“fast和”慢指针“slow一起一次走一步直至fast null结束这时slow指向的便是倒数第k个节点
代码如下
class Solution {public int kthToLast(ListNode head, int k) {if(head null) {return -1;}ListNode fast head;ListNode slow head;for(int i 0; i k; i) {fast fast.next;}while(fast ! null) {fast fast.next;slow slow.next;}return slow.val;}
}2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
题目链接CM11 链表分割
注意这题是将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序
public class Partition {public ListNode partition(ListNode head, int x) {// write code hereif(head null) {return null;}ListNode bs null;//bs:beforestartListNode be null;//be:beforeendListNode as null;//as:afterstartListNode ae null;//ae:afterendListNode cur head;while(cur ! null) {if(cur.val x) {if(bs null) {//找到bs和be的起始位置bs be cur;}else {be.next cur;be cur;}}else {if(as null) {//找到as和ae的起始位置as ae cur;}else {ae.next cur;ae cur;}}cur cur.next;}//ae的next需要手动置为nullif(ae ! null) {ae.next null;}//如果链表的节点都大于x则返回asif(bs null) {return as;}//bs不为nullbe自然也不为空be.next as;return bs;}
}2.6 判定链表是否是回文
题目链接OR36 链表的回文结构
public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code hereif(A null) {return false;}if(A.next null) {return true;}//1.找到中间节点ListNode mid getMiddleNode(A);//2.反转后半部分ListNode as reseverList(mid);mid.next null;//一定要置null//3.从前往后依次对比两个链表的val值是否相同ListNode bs A;while(bs.next ! null as.next ! null) {if(bs.val ! as.val) {return false;}bs bs.next;as as.next;}if(bs.val ! as.val) {return false;}return true;}private ListNode reseverList(ListNode head) {ListNode prev head;ListNode cur head.next;ListNode curN cur.next;while(cur ! null) {cur.next prev;prev cur;cur curN;if(curN ! null){curN curN.next;}}return prev;}private ListNode getMiddleNode(ListNode A) {ListNode fast A;ListNode slow A;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}2.7 判定链表相交并求出交点
题目链接160. 相交链表
解题思路
分别求出两个链表的长度并得到两链表的长度差值正数先让长链表的“l指针”走长度差值步再让“l指针”和“s指针”一起走如果相遇相遇点即为相交链表的交点如果没有相遇则最后l和s同时为null检验当两个链表同时为null时代码是否满足
代码如下
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA size(headA);int lenB size(headB);//先假设headA链表的长度大于headB链表ListNode l headA;ListNode s headB;int len lenA-lenB;//如果是headB链表更长则进入if语句进行调换if(len 0) {len -len;l headB;s headA;}for(int i 0; i len; i) {l l.next;}while(l ! s) {l l.next;s s.next;}if(l null) {return null;//没相交}return l;}public int size(ListNode head) {int len 0;ListNode cur head;while(cur ! null) {cur cur.next;len;}return len;}
}2.8 判断链表带环
题目链接141. 环形链表
解题思路
定义一对“快慢指针”快指针fast一次走两步慢指针slow一次走一步如果最后fast slow则说明该链表存在环形结构如果最后 fast null || fast.next null则说明该链表不存在环形结构检验链表为null时代码是否满足
代码如下
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;}
}2.9 求环的入口点
题目链接142. 环形链表 II
解题思路
先判断链表结构中是否存在环在2.8代码中进行略微修改即可求交点: 让一个引用从链表起始位置开始一个引用从相遇点位置开始两个引用每次都走一步最终相遇时的节点即为交点原因如下
数学推导 代码如下
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;//这个if语句必须放在下面否则该if语句第一次就会成立//因为fast和slow第一次都是headif(fast slow){break;}}if(fast null || fast.next null) {return null;}slow head;while(fast ! slow) {fast fast.next;slow slow.next;}return fast;}
}2.10 合并两个有序链表
题目链接21. 合并两个有序链表
解题思路
创建一个带头结点的单链表依次对比两个链表的数值大小小的尾插到新链表尾部当一个链表被新链表连接完时另一个链表剩下的部分直接尾插到新链表的尾部检验当一个链表为null时代码是否满足
代码如下
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode cur1 list1;ListNode cur2 list2;ListNode newHead new ListNode();//NewHead为带头结点ListNode curN newHead;while(cur1 ! null cur2 ! null) {if(cur1.val cur2.val) {curN.next cur1;cur1 cur1.next;} else {curN.next cur2;cur2 cur2.next;}curN curN.next;}if(cur1 null) {curN.next cur2;}if(cur2 null) {curN.next cur1;}return newHead.next;}
}
