在上一节,我们自己实现了一个单链表的结构,接下来我们来写几个面试题巩固一下

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;
        }
        //判断头结点是不key
        if (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;
            //跟新head
            head = cur;
            //跟新cur
            cur = curNext;
        }
        //返回head
        return 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-1
    public 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;
                 //跟新list1
                 list1 = list1.next;
             } else {
                 //小的话就把小的链接到newH上
                 tmpH.next = list2;
                 //跟新list2
                 list2 = 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;

    }