java数据结构与算法——链表面试题

发布时间:2023-08-08 18:30

本文为链表相关面试题,每道题均附讲解及对应连接。

一:反转一个单链表。

链接:206. 反转链表 - 力扣(LeetCode)https://leetcode.cn/problems/reverse-linked-list/description/

1.题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。2.

java数据结构与算法——链表面试题_第1张图片

2.解题

java数据结构与算法——链表面试题_第2张图片

         我的思路是:从第二个结点开始,依次将后一个结点的指向改变为指向前一个结点。如果直接改变指向,那么就无法找到下一个结点了,所以需要设置一个curNext,保存下一个结点。

        每次都让当前结点指向前一结点,然后head和cur都后移一个节点。直到cur == null时,说明反转结束,直接返回head结点即可。

java数据结构与算法——链表面试题_第3张图片

        具体代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
                    return head;
                }
                ListNode cur = head.next;
                ListNode curNext = new ListNode();
                head.next = null;
                while(cur != null){
                    curNext = cur.next;
                    cur.next = head;
                    head = cur;
                    cur = curNext;
                }
                return head;
    }
}

二:寻找链表的中间结点 

链接:

876. 链表的中间结点 - 力扣(LeetCode)https://leetcode.cn/problems/middle-of-the-linked-list/comments/

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

2.解题

        我们很容易想到先求出链表长度,再找到中间的结点,但是这种做法的时间复杂度较高。面对这类题时,比较常见的做法是使用“快慢指针”。

        设置fast和slow“指针”,slow指针走一步,fast指针走两步,这样当fast走到链表末尾时,slow恰巧到达链表的中间位置。

        具体代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {        
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;

    }
}

三:输出链表中倒数第k个结点

链接:

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

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

2.解题

        这道题任然可以沿用“快慢指针”的思路。让快指针先走k步,然后快慢指针一起走。当快指针走到链表的末尾时,慢指针所在的位置就是链表中倒数第k个结点。当然我们考虑的是最佳情况,而在解决问题时,最重要的就是要考虑到所有的情况。

        特殊情形1:k <= 0;直接返回null;

        特殊情形2:head == null;直接返回null;

        特殊情形3:在fast向后移动k个结点的过程中,fast指针为空了,说明整个链表的长度都不足k,当然不会有倒数第k个结点了,直接返回null。

具体代码如下:

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

 四:合并两个有序链表

链接:

21. 合并两个有序链表 - 力扣(LeetCode)https://leetcode.cn/problems/merge-two-sorted-lists/description/

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

java数据结构与算法——链表面试题_第4张图片

 2.解题

        两个链表的头节点分别是head1,head2。从头结点开始,依次比较两个链表结点值的大小,并将较小的那个节点加入到合并链表中,head1(head2)向后移动一位,继续比较剩下的结点。直到其中一个链表的所有节点都已加入到合并链表中,此时就将另一个链表中的剩余结点接到合并链表中,程序结束。

        本题整体思路比较简单,需要考虑的特殊情况是某个头节点为空两个头结点都为空时,无需进行合并,直接返回另一个节点的头结点即可。

具体代码如下:

public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        ListNode head = new ListNode();
        ListNode cur = head;
        while (head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                cur = cur.next;
                head1 = head1.next;
            }else{
                cur.next = head2;
                cur = cur.next;
                head2 = head2.next;
            }
        }
        if(head2 == null){
            cur.next = head1;
        }else{
            cur.next = head2;
        }
        return head.next;
    }

五:链表分割

链接:

链表分割_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

1.题目:现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

2.解题 

        使用两个链表,一个链表放小于x的结点,另一个链表放大于x的结点。遍历原链表结束后,就可以将所有小于x的结点放在第一个链表中,其余结点放在第二个链表中,且顺序不变。最后,将两个链表连接起来即可。

特殊情况及注意事项:

1.特殊情况:当链表为空时,直接返回null;

2.注意事项:连接两个链表后,一定要将第二个链表的next域置为null,否则会出现混乱。

具体代码如下:

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
//思路:
//1.分为两个链表,一个链表放小于x的节点,一个链表放大于等于x的节点
//2.连接两个链表
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode head1 = null;
        ListNode last1 = null;
        ListNode head2 = null;
        ListNode last2 = null;
        if(pHead == null){
            return null;
        }
        while(pHead != null){
            if(pHead.val < x){
                if(head1 == null){
                    head1 = pHead;
                    last1 = pHead;
                }else{
                    last1.next = pHead;
                    last1 = last1.next;
                }
            }
            else{
                if(head2 == null){
                    head2 = pHead;
                    last2 = pHead;
                }
                else{
                    last2.next = pHead;
                    last2 = last2.next;
                }
            }
            pHead = pHead.next;
        }
        //进行连接
        if(head2 == null){
            return head1;
        }
        if(head1 == null){
            return head2;
        }
        last1.next = head2;
        last2.next = null;//最后一个next域置为null
        return head1;
    }
}

六:链表的回文结构

链接:

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)icon-default.png?t=M4ADhttps://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

1.题目:

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

2.解题

        回文链表类似于这样的结构:1-3-4-4-3-1,显然从中间分开,两边对称。结合之前讲到的链表反转和寻找中间结点,我们考虑先找到中间结点,然后从中间结点开始,将其后的链表反转;然后遍历两个链表,依次比较每一个结点的值。如果其中两个结点的值不同,说明这不是一个回文串,返回false即可。图解如下:

java数据结构与算法——链表面试题_第5张图片

java数据结构与算法——链表面试题_第6张图片

         显然结点个数不同,判断结束的标志也有所差异,我们只需将这两种情况都添加到我们的判断语句中即可,当head == slow || head.next == slow时,表明每个节点都已经判断完毕,该链表是回文的,返回true。

具体代码如下:

import java.util.*;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
        //1.找到中间结点
        ListNode head = A;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时,slow已经指向中间的结点
        //2.从中间结点开始进行反转
     ListNode cur = slow.next;
            ListNode curNext = new ListNode(1);
            while(cur != null) {
                curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
        //反转成功,最开始有个head,最后面有个slow
        //3.从两边,向中间走
        while(head.val == slow.val){
            head = head.next;
            slow = slow.next;
            if(head == slow || head.next == slow){
                return true;
            }
        }
        return false;

    }
}

七:判断链表中是否有环

链接:

141. 环形链表 - 力扣(LeetCode)icon-default.png?t=M4ADhttps://leetcode.cn/problems/linked-list-cycle/description/

1.题目:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 

2.解题

        快慢指针。慢指针一次走一步,快指针一次走两步,如果链表中有环,快慢指针一定会相遇。

        具体代码如下:

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!= null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

八:环形链表

链接:

142. 环形链表 II - 力扣(LeetCode)icon-default.png?t=M4ADhttps://leetcode.cn/problems/linked-list-cycle-ii/description/

1.题目:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

2.解题:

        这是一个简单的数学问题。

java数据结构与算法——链表面试题_第7张图片

 java数据结构与算法——链表面试题_第8张图片

 具体代码如下:

/**
 * 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) {
         ListNode slow = head;
        ListNode fast = head;
        if(slow == null || slow.next == null) {
            return null;
        }
        ListNode k = head;  
        while(fast!=null && fast.next!= null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        while(slow != null ){
            if(slow == k){
                return slow;
            }            
            k = k.next;
            slow = slow.next;
        }
        return null;
    }
}

        以上就是关于链表的一些习题。“快慢指针”在解决链表问题时经常出现,我们一定要掌握好这种方法;其次,在解决题目六:链表的回文结构时,我们用到了“快慢指针”和“反转链表”的相关知识,很容易就解决了这个题目,这说明再解决一些较为复杂的问题时,可以将其拆分为一个个简单问题加以解决。

        链表题目浩如烟海,以上所展示的不过是沧海一粟罢了。笔者将力扣及牛客网上链表部分的链接放在下面,感兴趣的朋友可以自行选择练习。

链接:

链表知识点题库 - 力扣(LeetCode)icon-default.png?t=M4ADhttps://leetcode.cn/tag/linked-list/problemset/链表知识点题库 - 牛客网(nowCoder)icon-default.png?t=M4ADhttps://www.nowcoder.com/exam/oj

本课内容结束!


ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号