【数据结构】单链表面试题讲解-＞壹

痛定思痛。 2024-04-17 10:42 94阅读 0赞

#### 文章目录 ####

*  引言
 *  反转单链表
 *   *  题目描述
     *  示例：
     *  题解思路
     *  代码实现：
 *  移除链表元素
 *   *  题目描述：
     *  示例
     *  思路解析：
 *  链表的中间结点
 *   *  题目描述：
     *  示例：
     *  思路解析
     *  代码实现如下：
 *  链表中倒数第k个结点
 *   *  题目描述
     *  示例
     *  思路解析：
     *  代码实现如下：
 *  总结

## 引言 ##

单链表的操作算法是笔试面试中较为常见的题目。  
本文将着重介绍平时面试中常见的关于链表的应用题目，马上要进行秋招了。希望对你们有帮助 \_?  
![在这里插入图片描述][94b094fa0d0f42bcac0a437a41e1eff4.png]

## [反转单链表][Link 1] ##

### 题目描述 ###

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表\{1,2,3\}时，  
经反转后，原链表变为\{3,2,1\}，所以对应的输出为\{3,2,1\}。  
以上转换过程如下图所示：  
![在这里插入图片描述][e2827c3363bc41519134606fa53e948f.png]

### 示例： ###

![在这里插入图片描述][52a35795798e460687aff7f2e18e5f4a.png]

### 题解思路 ###

（1）定义两个指针： pser 和 sur ；sur 在前 pser 在后。  
![在这里插入图片描述][39abc27793004c1780be1a8dafb5dcad.png]  
（2）sur用于遍历，pser用于交换位置，并插入到头节点前面

（3）将head里面的next置为null

（4）每一次插入顺序为将sur的位置付给pser，然后sur向前走一步，令pser里的next设为head；这时候pser为头节点，我们再将pser赋给head作为新的头节点。每循环一次头节点向前走一步  
![在这里插入图片描述][907596453d864a5f84faa527d27f73a5.png]

（5）循环上述过程，直至 sur 到达链表尾部  
![在这里插入图片描述][3b616b0bf84947d19c25f77c782c6fc2.png]

### 代码实现： ###

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     *   public ListNode(int val) {
     *     this.val = val;
     *   }
     * }
     */
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param head ListNode类
         * @return ListNode类
         */
        public ListNode ReverseList (ListNode head) {
        
            // write code here
    
            if (head == null || head.next == null) {
        
                return head;
            }
    
            ListNode sur = head.next;
            ListNode pser = head;
            head.next = null;
            while (sur != null) {
        
                pser = sur;
                sur = sur.next;
                pser.next = head;
                head = pser;
            }
            return head;
        }
    }

## [移除链表元素][Link 2] ##

### 题目描述： ###

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

### 示例 ###

![在这里插入图片描述][1eae600e653649cab144a81c8351a859.png]

### 思路解析： ###

我们依旧需要对该单链表进行判断，如果为空，就直接返回

由于我们需要删除很多个这样的节点，但是我们的单链表却是单向的，按照上面的写法，我们则需要遍历很多次单链表，大大的增加了复杂度，我们为了降低时间复杂度，使它降为O(N);

我们设两个遍历节点，进行遍历，一个在前为cur，一个在后prev  
![在这里插入图片描述][58dcb97c5888489b85ff6b01ce069824.png]  
前面的cur负责进行遍历删除，后面的prev负责跟在cur后面记录cur的上一节点

当cur下一节点不是我们所要删除的元素时，这时候我们将prev变为我们当前节点的cur，而cur变为当前节点的next

![在这里插入图片描述][558410e43d7d4f0fab834c91a3b99025.png]  
当前的删除方法只能删除第一个节点以后的元素，所以我们还需要处理第一个元素是我们所需要删除的情况。

代码实现如下

/**
     * 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 removeElements(ListNode head, int val) {
        
            if(head == null) {
        
                return null;
            }
            ListNode prev = head;
            ListNode cur = head.next;
            while (cur != null) {
        
                if(cur.val == val) {
        
                    prev.next = cur.next;
                    cur = cur.next;
                }else {
        
                    prev = cur;
                    cur = cur.next;
                }
            }
            if(head.val == val) {
        
                head = head.next;
            }
            return head;
        }
    }

## [链表的中间结点][Link 3] ##

### 题目描述： ###

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

### 示例： ###

![在这里插入图片描述][c58193bab2e74db887912a46561f8d5b.png]

### 思路解析 ###

我们依旧两个定义两个指针，一个一次性走两步，一个一次性走一步

当快的指针到达终点时，慢的指针所☞指位置就是我们所需要的中间位置

就像大人与小孩子一起走路，大人的速度是小孩子的两倍  
![在这里插入图片描述][e5ecb2cb26254fc09c47a48cbd16551d.png]  
大人到达终点时，小孩子才走到一半！

### 代码实现如下： ###

注意：fast != null与fast.next != null不可以调换

## [链表中倒数第k个结点][k] ##

### 题目描述 ###

输入一个链表，输出该链表中倒数第k个结点。

### 示例 ###

> 输入：  
> 1,\{1,2,3,4,5\}  
> 返回值：  
> \{5\}

### 思路解析： ###

依旧是两个指针，分别为fast和slow，fast先出发，fast出发k-1步后，slow出发，中间保持k-1个节点的距离，fast所指向下一节点为null时结束

![在这里插入图片描述][c0a73ba18be84aa2877ec8858e2b73fb.png]

### 代码实现如下： ###

import java.util.*;
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        public ListNode FindKthToTail(ListNode head, int k) {
        
            if (k <= 0 || head == null) {
        
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            //1. fast走k-1步
            while (k - 1 != 0) {
        
                fast = fast.next;
                if (fast == null) {
        
                    return null;
                }
                k--;
            }
            //2、3、
            while (fast.next != null) {
        
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

## 总结 ##

关于《【数据结构】 单链表面试题讲解》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[94b094fa0d0f42bcac0a437a41e1eff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/322a8ff641574c6b8341f72ff1762e43.png
[Link 1]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=/exam/oj
[e2827c3363bc41519134606fa53e948f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/745e7dbbdbaf41889c9eaa13a035304a.png
[52a35795798e460687aff7f2e18e5f4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/08af082c9f744db4807cb9b4e0316093.png
[39abc27793004c1780be1a8dafb5dcad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/dd83991e98534faaafa74ca45a519c39.png
[907596453d864a5f84faa527d27f73a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/5ee7d2fd1a86486ea7c50b269dbdf330.png
[3b616b0bf84947d19c25f77c782c6fc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9885ee109fd14df08e6f812204de55af.png
[Link 2]: https://leetcode.cn/problems/remove-linked-list-elements/
[1eae600e653649cab144a81c8351a859.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/cc1997d7e1c24ef8b2163b93f8a6502b.png
[58dcb97c5888489b85ff6b01ce069824.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9e387120c9cd4ad19a6e317f53fa8db2.png
[558410e43d7d4f0fab834c91a3b99025.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/176b6daa02b04edfbe38dd0b151a309d.png
[Link 3]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[c58193bab2e74db887912a46561f8d5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/cb9d37d7dedc46849b768ef17784bf9d.png
[e5ecb2cb26254fc09c47a48cbd16551d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/fb740aa3d025431b8ffdd4df06290f84.png
[k]: https://editor.csdn.net/md?not_checkout=1&spm=1015.2103.3001.8066&articleId=132380598
[c0a73ba18be84aa2877ec8858e2b73fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ab00a1ef9ece4cfaa7aeb595876fe317.png