自学内容网 自学内容网

链表面试练习习题集(Java)

1.

思路:

因为杨辉三角是由二维数组构成,所以要先创建一个二维数组,如何用顺序表表示二维数组,可以通过List<List<Interger>>来表示一个二维数组,可以这样理解:先创建一个一维数组List,然后这个一维数组里面存放的元素类型是:<List<Integer>>,即接收整型的一维数组,所以一个一维数组中每个元素存的还是一维数组,那么就相当于二维数组了。

然后杨辉三角每行的第一列为1,则add(1)即可,中间为上一行对齐的两个元素之和,所以要先通过对二维数组get得到上一行的数组,再通过对上一行的数组get得到对齐的那两个元素,最后将和add到这一行的一维数组里,如此类推

最后每一行的最后一列元素也是1,因为add的底层实现是尾插,所以我们直接add(1)即可,最后再将这一行的一维数组add到二维数组里

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new ArrayList();//二维数组
        List<Integer> list1=new ArrayList<>();//一维数组
        list1.add(1);
        list.add(list1);
        for (int i = 1; i < numRows; i++) {
            //第一列
            List<Integer> curRow=new ArrayList<>();
            curRow.add(1);
            //中间
            List<Integer> preRow=list.get(i-1);
            for (int j = 1; j < i; j++) {
                int a=preRow.get(j-1);
                int b=preRow.get(j);
                curRow.add(a+b);
            }
            //最后一列
            curRow.add(1);
            list.add(curRow);
        }
        return list;
    }
}

2.

思路:

看到求中间的东西,大概率会用到快慢指针,即当慢指针走一步,快指针走两步,当快指针到达终点时,慢指针刚好在中间,因为很简单的公式:路程=速度*时间;时间t相等,v快=2v慢,s=v快*t,v慢*t=1/2s

当结点为奇数个数时,刚好为中间的结点,当结点为偶数个数,为中间的第二个结点,根据快慢指针一个走两步,一个走一步,刚刚好都满足,所以就不用分类讨论了

什么时候停止指针移动呢,根据示例1和2,在示例1中,当快指针在5这里停止,在示例2中,当快指针在6的后面(即null)这里停止,所以循环条件为fast!=null&&fast.next!=null,注意&&前后两个条件不能换,必须先fast!=null再fast.next!=null,因为互换的话,当fast==null时,fast.next会报异常

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;//走一步
            fast=fast.next.next;//走两步
        }
        return slow;
    }
}

3.

思路:

需要两个指针,一个记录当前结点cur,一个记录前面的那个结点precur,一开始都指向头结点head。如果cur的val等于传入的val,则先将cur往后移动一位,然后precur.next指向cur;否则precur走到cur的位置,cur往后移一步,循环条件为cur!=null,这是一般情况的代码

如果一开始头结点就等于val,即示例3的情况,那么按照上面的代码就不能将头结点移除,所以我们要判断一开始头结点是否为val,如果为val,则新头结点为头结点的后一个,因为移除完后的新头结点有可能仍然等于val,所以不是用if而是while,如果头结点为null,则说明全是val,如示例3的情况,此时就返回新头结点(也就是null)

一般都是先考虑正常情况,然后再来考虑特殊情况

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        //解决一开始头结点的值就为val
        while(head.val==val){
            head=head.next;
            if(head==null){
                return head;
            }
        }
        //说明此时头结点一定不为val
        ListNode cur=head;//当前结点
        ListNode precur=head;//前结点
        while(cur!=null){
            if(cur.val==val){
                cur=cur.next;
                precur.next=cur;
            }else{
                precur=cur;
                cur=cur.next;
            }
        }
        return head;
        }
}

4.

思路:

因为是反转,所以可以确定的是,第一个结点反转后一定是最后一个结点,所以我们要将头结点的next改为null,但改之前要记录头结点的下一个结点。然后采用每遍历一个结点就进行头插,即该结点cur的next指向头结点,但修改next的指向时,要先将原来的next指向的结点进行保存,保存到curN,然后头插完,cur=curN,循环条件为cur!=null

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return head;
        }
        //必要处理
        ListNode cur=head.next;//第一步:记录头结点的next结点
        head.next=null;//第二步:头结点的next改为null
        //循环遍历,使用头插
        while(cur!=null){
            ListNode curN=cur.next;//循环中的第一步:记录下一个结点
            cur.next=head;//第二步:当前结点头插到头结点之前
            head=cur;//第三步:新的头结点为当前结点
            cur=curN;//第四步:当前结点后移到原来的下一个结点位置
        }
        return head;
    }
}

5.

思路:

法一:可以利用我们刚刚上面那道题的代码,先将链表反转,再遍历第k个结点即可

法二:遍历两次,第一次求长度len,第二次遍历到第len-k个结点即可

法三:利用集合顺序表arraylist,遍历一次,用add将里面所有的元素放进顺序表里,然后再get(arraylist.size()-k)即可

法四:快慢双指针,先提前让快指针走k步,然后慢指针和快指针以相同的速度每次走一步,当快指针走到最后时,慢指针的位置即为倒数第k个结点

示例代码(法一)

class Solution {
    public int kthToLast(ListNode head, int k) {
        if(head==null){
            return -1;
        }
        //反转链表
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        //然后找
        ListNode node=head;
        for(int i=1;i<k;i++){
            node=node.next;
        }
        return node.val;
    }
}


原文地址:https://blog.csdn.net/2301_80369371/article/details/140502549

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!