在上一节,我们自己实现了一个单链表的结构,接下来我们来写几个面试题巩固一下
1. 删除链表中等于给定val的所有结点
解析题目:
如图,我们需要删除所有的值为12的结点
在head非空的情况下,我们删除一个结点,首先要找到这个结点,然后把这个结点的前面一个结点的next指向这个节点的下一个,这个就是总体的步骤,不过我们不止删除一个结点,我们需要删除所有是val值的结点,因此综上,我们需要俩个指针,prev和cur,prev指向的是删除结点的前一个结点,cur就是删除结点的当前节点,因此我们一开始先设置prev = head,cur = head.next;然后我们进入循环,如果当前的cur.val==key,我们就需要让prev.next = cur.next,然后我们需要跟新cur,cur = cur.next,如果我们当前节点的值不等于key,那么我们需要让prev = cur;cur=cur.next;
上面就大致解决了这个问题,但是我们还漏了一点,那就是head节点,head节点我们并没有判断它是否和val值一致.并且这行代码必须在删除完中间节点之后再删除,不然要用while,因为我们考虑到这种情况:1,1,1,2,2,1;我们如果一开始就删去1,那么第二个1是不可能被删除的,因为我们后期也没处理新的头结点的key,这一点同样也要在上一节博客修改一下.
整体代码:
public void removeAllKey(int key) {//判断头节点是不是空的if (this.head == null) {return;}//判断头结点是不keyif (head.val == key) {this.head = this.head.next;}ListNode prev = head;ListNode cur = head.next;//我们遍历除了head后面的元素while (cur != null) {if (cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}}2. 翻转一个单链表
解析题目:
我们翻转一个链表,也就是要把从最后一个节点开始,把它的next指向它的前一个
此时,我们可以采用头插法来,我们用cur记录当前节点,cur = head.next;然后我们需要把head.next置空,因为此刻head指向的节点是相当于我们翻转之后的最后一个节点.然后我们在把cur插到head前面的时候,我们需要用curNext来记录后面的节点,不然后续我们头插完,就找不然原先的链表了.然后我们需要跟新head,head = cur完成一轮插入,然后我们需要跟新cur,让cur指向curNext,再让curNext记录下一个节点.
还有个小地方,也就是我们如果链表head == null 或者head.next == null我们直接返回head即可,因为没有必要翻转.
整体代码:
//TODO 翻转链表public ListNode reverseList() {//判断链表是不是空的if(head == null) {return null;}//如果只有一个结点,就直接返回head即可if(head.next == null){return head;}//其他情况就用头插法ListNode cur = head.next;head.next = null;while (cur != null) {//把head置空//记录下一个节点的位置ListNode curNext = cur.next;//把cur头插进去cur.next = head;//跟新headhead = cur;//跟新curcur = curNext;}//返回headreturn head;}3. 给定一个带有头节点的非空单链表,返回链表的中间结点.如果有俩个中间结点,则返回第二个中间结点.
解析题目:
我们可以看见,我们返回中间结点,要分偶数个结点和奇数个结点.
我们先来看法1: 1> 求出整个链表的大小;2>找到len/2的结点
因为过于简单,我们这里就不画图了,直接解释代码:
先判断整个链表head是不是null;然后进入主题,求len,我们的循环条件是cur!=null,因为我们需要遍历所有的结点,如果用cur.next!=null;我们就会漏掉最后一个结点.然后注意,我们需要让cur重新指向head,因为cur刚刚在遍历的时候已经为null了;我们再设置一个计数变量i,中间长度mid,我们每次cur-cur.next;我们就需要对i进行++;
public ListNode middleNode() {if(head==null){return null;}//先求整个链表的长度int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}cur = head;//再求长度/2找到这个中间节点int mid = len / 2;int i = 0;while (i != mid) {cur = cur.next;i++;}return cur;}法2 快慢指针,一开始fast和slow都指向head,然后fast走俩步,slow走一步;
这里因为奇偶数结点会分俩个情况,fast结束的标志会有俩种情况,也就是:fast == null和fast.next == null;在fast满足上面的情况之一就会说明slow到达了中间结点了.
这里我们解决俩个问题即可:
1> 为什么先判断fast再判断fast.next;
2> 为什么不能用||要用&&
整体代码:
public ListNode middleNodeFastAndSlow() {if(head == null){return null;}//我们定义俩个指针ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {//fast一次走俩步,slow一次走一步fast = fast.next.next;slow = slow.next;}return slow;//俩个点//1.为什么不能用||要用&& 因为如果是偶数个,最后我们fast会为null,因此判断fast.null会显示空指针异常//2.为什么先要判断fast,再判断fast.next:因为如果是偶数个,fast最后会走到null,这时候先判断fast.next!=null会空指针异常}4. 输入一个链表,输出该链表中倒数第k个结点
题目解析:
这个题目其实也有俩个方法,但是我们这里主要用快慢指针来解题
假设我们求的是倒数第k个结点,我们先让fast先走k-1步,然后我们再让fast和slow一起走,直到fast ==null为止;这个东西我是这么理解的,我们相当于把fast作为一个我们自定义的动态边界条件,让它先走k-1步,再同时走,这样fast肯定会先到最后一个结点,然后此时我们的slow所在位置就是倒数第k个结点.slow和fast相差k-1步.
然后我们这里要判断我们所要的结点的下标的合法性,此时我们我们可以优化一下k>size()这个条件,因为如果k很大,我们要遍历O(n),因为我们的fast要走k-1步,此时我们也需要一个循环,所以,我们直接去在这里面判断fast == null
整体代码:
//TODO 输出链表倒数第k个结点//slow和fast总是差k-1public ListNode FindtheToTail(int k) {//先判断k的合法性if(k < 0) {//我们可以优化一下这个k>siez()return null;}//并且判断head是不是空if (head == null) {return null;}ListNode fast = head;ListNode slow = head;//fast走k-1步for (int i = 0; i < k-1; i++) {fast = fast.next;//TODO 优化size()不去遍历,这个就是去处理k太大的情况if(fast == null) {return null;}}//同时走while (fast != null) {fast = fast.next;slow = slow.next;}//fast到最后,slow的位置就是倒数第k个return slow;}5. 将俩个有序链表合并成一个新的有序链表并返回.
题目解析:
差不多是这么个情况,我们有俩个有序的链表,我们要把俩个合并成一个新的有序链表.我们先构造一个虚拟结点newH,然后我们再让list1和list2(此处,图上的head1就是list1,head2就是list2)互比较,小的就把该结点尾插到newH上去
具体步骤如图,我们要记录虚拟结点的位置,因此创建一个tmpH指向一开始的newH,我们把list1和list2的val进行比较,小的那一方,把该结点和newH连接在一起,如果是list1小,那么tmpH.next = list1;然后我们跟新list1,list=list.next;然后我们也要跟新newH,因为它指向的是链表的尾巴,我们进行尾插法,直到有一个链表为空为止
我们如图可以知道list2已经遍历完了,我们直接把list1剩下的元素连接过来即可,最后我们返回headH.next即可(因为headH是个虚拟结点)
整体代码:
//TODO 合并俩个有序列表public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {//先生成一个开头的结点MySingleList.ListNode newH = new MySingleList.ListNode(-1);//tmpH始终指向的是链表的尾巴MySingleList.ListNode tmpH = newH;//判断俩个链表是不while (list1 != null && list2 != null) {//先比较list1和list2指向的结点,我们把小的值链接上if(list1.val < list2.val) {//小的话就把小的链接到newH上tmpH.next = list1;//跟新list1list1 = list1.next;} else {//小的话就把小的链接到newH上tmpH.next = list2;//跟新list2list2 = list2.next;}System.out.println("while末尾");//tmpH始终指向的是链表的尾巴tmpH = tmpH.next;}//如果其中一个为空了,那么就把另外一个链接过来即可if(list1 != null) {tmpH.next = list1;}if (list2 !=null){tmpH.next = list2;}return newH.next;}