网站不足之处,西安网站seo,百度商桥网站加不上,做博客网站要怎么配置的服顺序表与链表LinkedList 选择题链表面试题1. 删除链表中等于给定值 val 的所有节点。2. 反转一个单链表。3. 给定一个带有头结点 head 的非空单链表#xff0c;返回链表的中间结点。如果有两个中间结点#xff0c;则返回第二个中间结点。4. 输入一个链表#xff0c;输出该链… 顺序表与链表LinkedList 选择题链表面试题1. 删除链表中等于给定值 val 的所有节点。2. 反转一个单链表。3. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。4. 输入一个链表输出该链表中倒数第k个结点。5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。6. 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。7. 链表的回文结构。8. 输入两个链表找出它们的第一个公共结点。9. 给定一个链表判断链表中是否有环。10. 给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL11. 删除链表中重复的结点 选择题
1 A错误头插不需要遍历链表与链表长度无关 B错误尾插不需要遍历链表因为有一个引用指向了尾结点可以直接插入 C错误删除第一个节点也不需要遍历链表 D正确删除最后一个节点之前先要把倒数第二个节点找到因为最后一个节点删除之后需要将倒数第二个节点的next置为null 故需要遍历链表 因此选择D 2 答案D 解析二叉树属于树形结构不是线性的队列链表顺序表都属于线性表 3 答案D 解析链表的插入和删除不是所有情况下都比顺序表快比如尾插尾删顺序表的时间复杂度为O1并且如果是单链表如果要在中间某个节点的前面插入/删除一个节点则需要遍历。所以时间的快慢要分情况看待。 4 5 A错误ArrayList中的元素不一定有序ArrayList没有要求里面的元素必须有序可能有序也可能不有序 B正确ArrayList中的元素可以通过下标修改 C错误ArrayList中的元素没要求必须要唯一可以唯一也可以重复 D错误ArrayList中的元素是通过下标访问的而不是通过key 故正确应该选B 6 A正确ArrayList 和 LinkedList都是实现了List接口 B正确ArrayList是动态类型顺序表插入时当空间不足时会自动扩容 C正确LinkedList底层是链表结构链表不支持随机访问如果要访问任意元素只能通过查找处理 D错误LinkedList中插入或者删除元素只需要修改几个引用的指向即可不需要搬移愿意时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移时间复杂度O(N)
链表面试题
1. 删除链表中等于给定值 val 的所有节点。
OJ链接
class Solution {public ListNode removeElements(ListNode head, int val) {if(headnull){return null;}ListNode curhead.next;ListNode prevhead;while(cur!null){if(cur.valval){prev.nextcur.next;curcur.next;}else{prevcur;curcur.next;}} if(head.valval){headhead.next;} return head;}
}2. 反转一个单链表。
OJ链接
class Solution {public ListNode reverseList(ListNode head) {if(headnull){return null;}if(head.nextnull){return head;}ListNode curhead.next;head.nextnull;while(cur!null){ListNode curNextcur.next;cur.nexthead;headcur;curcurNext;}return head;}
}3. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。
OJ链接
class Solution {public ListNode middleNode(ListNode head) {ListNode slowhead;ListNode fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}return slow;}
}4. 输入一个链表输出该链表中倒数第k个结点。
OJ链接
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {int n Integer.parseInt(sc.next());ListNode head new ListNode(-1);ListNode temp head;//生成链表for (int i 0; i n; i) {ListNode node new ListNode(sc.nextInt());temp.next node;temp temp.next;}int k Integer.parseInt(sc.next());//使用快慢指针if(getKthFromEnd(head.next,k) ! null){System.out.println(getKthFromEnd(head.next,k).val);}else{System.out.println(0);}}}//通过快慢指针搜索public static ListNode getKthFromEnd(ListNode head,int k){if(k0||headnull){return null;}ListNode fasthead;ListNode slowhead;for(int i0;ik-1;i){fastfast.next;}while(fast.next!null){fastfast.next;slowslow.next;}return slow;}
}
class ListNode{ListNode next;int val;ListNode(int val){this.valval;nextnull;}
}5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
OJ链接
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHeadnew ListNode();ListNode tmpHeadnewHead;while(list1!nulllist2!null){if(list1.vallist2.val){tmpHead.nextlist2;list2list2.next;}else{tmpHead.nextlist1;list1list1.next;}tmpHead tmpHead.next;}if(list1!null)tmpHead.nextlist1;if(list2!null)tmpHead.nextlist2;return newHead.next;}
}6. 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。
OJ链接 有个易错不容易注意到如果ae.next!null链表会循环 此时应该将ae.nextnull 还要设想所有数都会大于x的可能此时会bsnull 直接return as即可
import java.util.*;/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode bsnull;ListNode benull;ListNode asnull;ListNode aenull;ListNode curpHead;while(cur!null){if(cur.valx){//第一次插入if(bsnull){bsbecur;}else{be.nextcur;becur;//或bebe.next;}}else{if(asnull){asaecur;}else{ae.nextcur;aecur;//或aeae.next;}}curcur.next;}//第一个段没有数据if(bsnull)return as;be.nextas;//防止最大的数据不是最后一个if(ae!null)ae.nextnull;return bs;}
}7. 链表的回文结构。
OJ链接 若偶数时 则循环到最后head.nextslow即可确定true
import java.util.*;/*
public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereListNode slowhead;ListNode fasthead;//用快慢指针确定链表中点while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}ListNode curslow.next;//翻转后段链表while(cur!null){ListNode curNextcur.next;cur.nextslow;slowcur;curcurNext;}while(head!slow){if(head.val!slow.val)return false;if(head.nextslow) //偶数 head和slow不会相遇时return true;headhead.next;slowslow.next;}return true;}
}8. 输入两个链表找出它们的第一个公共结点。
OJ链接
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//分别求2个链表的长度ListNode pLheadA;ListNode pSheadB;int lenA0;int lenB0;while(pL!null){lenA;pLpL.next;}while(pS!null){lenB;pSpS.next;}pLheadA;pSheadB;//保证pL指向最长的链表pS指向最短的链表len0int lenlenA-lenB;if(len0){pLheadB;pSheadA;lenlenB-lenA;}//2.让最长的链表先走差值步while(len!0){pLpL.next;len--;}//3.就是相遇的点while(pL!pS){pLpL.next;pSpS.next;}return pL;}
}9. 给定一个链表判断链表中是否有环。
OJ链接
【思路】 快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。比如陪女朋友到操作跑步减肥。
【扩展问题】
为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情况因此在慢指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。快指针一次走3步走4步…n步行吗
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(headnull)return false;//可以不写ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(fastslow)return true;}return false;}
}10. 给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL
OJ链接
结论 让一个指针从链表起始位置开始遍历链表同时让一个指针从判环时相遇点的位置开始绕环运行两个指针都是每次均走一步最终肯定会在入口点的位置相遇。证明
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(headnull)return null;ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(fastslow)break;}if(fastnull||fast.nextnull)return null;fasthead;while(fast!slow){fastfast.next;slowslow.next;}return fast;}
}11. 删除链表中重复的结点
OJ链接 易忽略的点应将手动将tmpHead.next置空防止后边到最后一个节点都是重复节点
import java.util.*;
/*public class ListNode {int val;ListNode next null;ListNode(int val) {this.val val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead) {ListNode curpHead;ListNode newHeadnew ListNode(-1);ListNode tmpHeadnewHead;//遍历每一个节点while(cur!null){if(cur.next!nullcur.valcur.next.val){//一直让cur走到不重复的节点 while(cur.next!nullcur.valcur.next.val){curcur.next;} curcur.next;}else{//把这个节点加入到不重复链表中tmpHead.nextcur;tmpHeadtmpHead.next;curcur.next;}}//手动将tmpHead.next置空防止后边到最后一个节点都是重复节点 tmpHead.nextnull;return newHead.next;}
}
