亲宝软件园·资讯

展开

Java 链表

K稳重 人气:0

前言:

上一章更到了链表,虽然知道了什么是链表,链表的结构是怎么样的,但这是远远不够的,我们只清楚了点皮毛,如果让你做题你还是会无从下手,所以我们必须多做题,在做题的过程中慢慢的我们就会觉得一切都很简单。下面我们就来做几道经典的链表面试题!!!!!!

第一题

题目:反转一个单链表

每个节点是不变的,只是修改当前每个节点的指向

看图分析:

问题分析:

每个节点是不变的,只需要修改当前每个节点的指向,第一个节点指向变成null,第二个节点的指向是第一个节点。

问题讲解:

我们需要定义四个节点变量

head变量等于头节点

cur = head

prev = null

curNext = cur.next

第一步:curNext = cur.next

第二步:cur.next = prev

第三步:prev = cur

第四步:cur = curNext

我们看一下图解是如何走的

第一步:curNext = cur.next

第二步:cur.next = prev

第三步: prev = cur

第四步: cur = curNext

这四步让它是一个循环,我们再走一个循环给大家看

第五步: curNext = cur.next

第六步: cur.next = prev

第七步: prev = cur

第八步: cur = curNext

这样两个循环下来我想大家看的就很明白了,那既然是循环肯定会有终止条件,所以我们可以看一下,当cur走到最后一个字节的时候,我们仍然需要 cur.next =  prev,再往后走的话cur就为null了,为null的时候就反转结束了。所以我们循环的终止条件就是cur != null。另外我们还需要判断一直指向头节点的head为不为null,如果为null的话就是没有这个链表,直接返回null就可以了。反转完成后最后一个节点就变成了头节点,所以我们返回prev就可以了、那我们就可以来写代码了。

代码实现:

lass Solution {
    public ListNode reverseList(ListNode head) {
         if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode prev = null;
 
        while (cur != null) {
            ListNode cutNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = cutNext;
        }
        return prev;
 
    }
}

力扣

https://leetcode-cn.com/problems/reverse-linked-list/description/

题目链接在上面,大家一定打开链接自己做一下。

第二题

题目:给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 

画图分析:

 问题分析:奇数的话返回中间的节点,偶数的话返回第二个中间节点,也就是说偶数返回第三个。

问题讲解:

同样的,我们来定义两个引用变量

fast,slow两个引用变量都等于head头节点

如图:

我们让fast一次走两步,slow一次走两步,奇数情况:fast.next为null,slow所在的就是中间节点位置 。偶数情况:fast为null,low所在的就是中间节点位置 。原因是为什么呢?两个同时走,fast的速度是slow的两倍,那么路程也是两倍,一个走到终点了,那么另一个就是走了路程的一半。有这样的思路我们就可以来写代码了 ,同样的先要判断一下链表是不是为null,为null直接返回null就好了

代码实现:

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

力扣

https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

第三题

题目:输入一个链表,输出该链表中倒数第k个结点

画图分析:

问题讲解:

同样的,我们来定义两个引用变量

fast,slow两个引用变量都指向头节点

如图: 

如果我们要找倒数第K个,从第K个到倒数第1个需要走K-1步,所以我们先让fast走K-1步,当走完K-1步,fast指向的是倒数第一个时候,那么slow就是我们要找的倒数第K给,如果fast走完K-1步,fast指向的不是倒数第一个,那么这个时候我们让fast和slow一起往后走,他们始终差了K-1步,当fast 走到倒数第一个的时候,这个时候slow所指向的节点就是我们要找的倒数第K个。这里K我们也要判断一下,如果K<=0 或者 k>链表的长度,我们直接返回null就可以了。

代码实现:

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0 || head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k-1 != 0){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            k--;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
        
    }
}

题目链接

第四题

题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

画图分析:这是我们的两个链表 

 问题讲解:

同样的,先定义两个引用变量headA和headB分别指向两个链表的头节点。

定义一个虚拟节点,假设叫newHead,在定义一个引用变量tmp等于newHead

 首先我们先来比较headA和headB的大小,如果headA.val<headB.val,那么就让tmp.next等于headA

 因为12小,那么就让headA = headA.next,如果后面再找到比12大数字就要放在12的后头,所以我们让tmp = tmp.next,

这个时候再比较headA和headB, 如果headA.val>headB.val,那么就是让tmp.next = headB,再让headB = headB.next,tmp = tmp.next

 这样就构成了我们的一个循环,当headA和headB都不为null的时候我们才能继续循环,当循环结束,要么headA为null,要么headB为null,当headA为null,我们让tmp.next = headB,当headB为null,我们让tmp.next = headA,

代码实现:

lass Solution {
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
 ListNode newhead = new ListNode(-1);
       ListNode tmp = newhead;
       while (headA != null && headB != null) {
           if (headA.val < headB.val) {
               tmp.next = headA;
               headA = headA.next;
               tmp = tmp.next;
           } else {
               tmp.next = headB;
               headB = headB.next;
               tmp = tmp.next;
           }
       }
           if(headA == null){
               tmp.next = headB;
           }
           if(headB == null){
               tmp.next = headA;
           }
       return newhead.next;
 
    }
}

 力扣

https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

因为时间原因:今天就先打卡这4道面试题,这4道面试题都是比较经典的面试题,对我们链表这块的学习会很有帮助。学习数据结构就是要多刷题,这样你才能完全掌握数据结构这门知识。今天太晚了,明天再继续给大家更面试题吧。有任何疑问大家都可以私信我,有问题欢迎大家指出来,我都会虚心学习的,希望可以和大家一起进步。

加载全部内容

相关教程
猜你喜欢
用户评论