数据结构 - 链表 - 面试中常见的链表算法题

小灰灰 2022-06-01 02:25 232阅读 0赞

## 数据结构 - 链表 - 面试中常见的链表算法题 ##

数据结构是面试中必定考查的知识点，面试者需要掌握几种经典的数据结构：**线性表**（数组、链表）、**栈与队列**、**树**（二叉树、二叉查找树、平衡二叉树、红黑树）、**图**。

本文主要介绍线性表中的常见的**链表**数据结构。包括

*  概念简介
 *  链表节点的数据结构（Java）
 *  常见的链表算法题（Java）。

--------------------

### 概念简介 ###

**如果对链表概念已经基本掌握，可以跳过该部分，直接查看常见链表算法题。**

#### 线性表基本概念 ####

链表是一种线性表，因此我们首先了解一下什么是线性表：

**线性表**是最常用且最简单的一种数据结构，它是n个数据元素的有限序列。实现线性表的方式一般有两种：

*  使用**数组**存储线性表的元素，即用一组连续的存储单元依次存储线性表的数据元素。
 *  使用**链表**存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。

#### 链表基本概念 ####

**链表**是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

**链表**由一系列**结点**（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的**数据域**，另一个是存储下一个结点地址的**指针域**。

相比于**线性表顺序结构（数组）**，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的**内存动态管理**。但是链表失去了**数组随机读取**的优点，同时链表由于增加了**结点的指针域**，**空间开销比较大**。  
**链表最明显的好处**就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表有很多种不同的类型：**单向链表**，**双向链表**以及**循环链表**。

#### 数组和链表的区别 ####

*  数组是同类型的连续的一个存储空间，链表是不连续的，其元素结点是一个结构体。
 *  数组是在栈中分配的，即数组大小在编译时就已经确定，即内存是静态分配的；链表是在堆中分配的，运行过程才具体分配，即链表是动态分配内存。
 *  数组对于元素的查询是通过下标直接索引，而链表是通过结点之间的链接一步一步进行遍历。数组对元素的查询时间复杂度是O(1)，链表对元素的查询时间复杂度是O(n).
 *  数组对于元素的插入、删除效率较低，需要进行挪位。而链表插入，删除只需要操作相应位置上的指针即可。数组对元素的插入、删除时间复杂度是O(n)，链表对元素的插入、删除时间复杂度是O(1)。

--------------------

### 链表节点的数据结构 ###

**链表**由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

定义节点为类：ListNode。具体实现如下：

public class ListNode {
    
        public int val; // 数据域
        public ListNode next; // 指针域
    
        public ListNode() {
    
        }
    
        public ListNode(int val) {
            this.val = val;
        }
    
        // 打印链表节点元素值
        public static void printList(ListNode head) {
            while (head != null) {
                System.out.print(head.val + "->");
                head = head.next;
            }
            System.out.println("null");
        }
    
    }

--------------------

### 常见的链表算法题（单链表） ###

##### 1. 求单链表中结点的个数 #####

/**
     * 1. 求单链表中节点的个数：
     * 注意检查链表是否为空。时间复杂度为O（n）。这个比较简单。
     * @param head 链表头结点
     * @return 链表中节点的个数
     */
    public static int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        int length = 0;
        ListNode current = head;
        while (current != null) { // 当前元素不为空
            length++;
            current = current.next;
        }
        return length;
    }

##### 2. 查找单链表中的倒数第k个结点（剑指offer，题15） #####

思路：这里需要声明两个指针：即两个结点型的变量first和second，首先让first和second都指向第一个结点，然后让second结点往后挪k-1个位置，此时first和second就间隔了k-1个位置，然后整体向后移动这两个节点，直到second节点走到最后一个结点的时候，此时first节点所指向的位置就是倒数第k个节点的位置。时间复杂度为O（n）。

/**
     * 2. 查找单链表中的倒数第k个结点（剑指offer，题15）
     * 时间复杂度为O（n）
     *
     * 考虑k=0和k大于链表长度的情况
     * @param head 链表头结点
     * @param k 倒数第k
     * @return 倒数第k个节点
     */
    public static ListNode findLastNode(ListNode head, int k){
        if (head == null || k <= 0) { // 输入异常
            throw new RuntimeException("输入参数格式不对...");
        }
        ListNode first = head; // 两个指针
        ListNode second = head;
        for (int i = 0; i < k - 1; i++) {
            second = second.next;
            if (second == null) { // 说明k的值大于链表的长度
                throw new RuntimeException("k越界");
            }
        }
        // 两个指针同时移动，second到达尾节点时，first是倒数第k个节点
        while (second.next != null) {
            first = first.next;
            second = second.next;
        }
        return first;
    }

##### 3. 查找单链表中的中间结点 #####

面试官不允许你算出链表的长度，该怎么做呢？  
思路：和上面的第2节一样，也是设置两个指针first和second，只不过这里是，两个指针同时向前走，second指针每次走两步，first指针每次走一步，直到second指针走到最后一个结点时，此时first指针所指的结点就是中间结点。

注意链表为空，链表结点个数为1和2的情况。时间复杂度为O（n）。

/**
     * 3. 查找单链表中的中间结点：
     * 上方代码中，当n为偶数时，得到的中间结点是第n/2个结点。比如链表有6个节点时，得到的是第3个节点。
     * @param head 链表头结点
     * @return 中间节点
     */
    public static ListNode findMidNode(ListNode head){
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode first = head;
        ListNode second = head;
        while (second.next != null && second.next.next != null) {
            first = first.next;
            second = second.next.next;
        }
        return first;
    }

##### 4. 合并两个有序的单链表，合并之后的链表依然有序【出现频率高】（剑指offer，题17） #####

这道题经常被各公司考察。例如：

链表1：1->2->3->4；
    链表2：2->3->4->5；
    合并后：1->2->2->3->3->4->4->5

解题思路：挨个比较链表1和链表2。这个类似于归并排序。  
尤其要注意两个链表都为空、和其中一个为空的情况。  
只需要O(1)的空间。时间复杂度为O (max(len1,len2))。

/**
     * 4. 合并两个有序的单链表，合并之后的链表依然有序【出现频率高】（剑指offer，题17）
     *  解题思路：挨着比较链表1和链表2。这个类似于归并排序。尤其要注意两个链表都为空、和其中一个为空的情况。
     *  只需要O(1)的空间。时间复杂度为O (max(len1,len2))
     * @param head1 链表1头结点
     * @param head2 链表2头结点
     * @return 合并后的链表头结点
     */
    public static ListNode mergeLinkList(ListNode head1, ListNode head2) {
        // 第一个链表为空
        if (head1 == null) {
            return head2;
        }
        // 第二个链表为空
        if (head2 == null) {
            return head1;
        }
        // 设置链表头结点
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) { // 链表1的元素小于链表2的元素
                temp.next = head1;
                head1 = head1.next;
            } else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        // 链表1没有遍历结束
        if (head1 != null) {
            temp.next = head1;
        }
        // 链表2没有遍历结束
        if (head2 != null) {
            temp.next = head2;
        }
        return head.next; // 返回空节点的下一个节点
    }

##### 5. 单链表的反转：【出现频率最高】（不使用额外的空间） #####

例如：

链表：1->2->3->4     
    反转之后：4->3->2->1

思路：从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。  
注意链表为空和只有一个结点的情况。时间复杂度为O（n）。

/**
     * 5. 单链表的反转：【出现频率最高】（不使用额外的空间）
     * 例如链表：1->2->3->4     反转之后：4->3->2->1
     * 思路：从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。
     * 注意链表为空和只有一个结点的情况。时间复杂度为O（n）
     * @param head 链表头结点
     * @return 链表反转后的头结点
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = null; // 保存链表新表头
        ListNode current = head; // 保存当前链表的遍历节点
        while (current != null) {
            ListNode next = current.next; // 保存当前节点的下一个节点
            current.next = newHead;
            newHead = current;
            current = next;
        }
        return newHead;
    }

##### 6. 从尾到头打印单链表 #####

**递归实现**：用递归实现，但有个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。

/**
    * 6.从尾到头打印单链表
    * 用递归实现，但有个问题：当链表很长的时候，就会导致方法调用的层级很深，有可能造成栈溢出。
    * 注意链表为空的情况。时间复杂度为O（n）
    * @param head 链表头结点
    */
    public static void reversePrint(ListNode head) {
       if (head == null) {
           return;
       }
       reversePrint(head.next);
       System.out.print(head.val + "->");
    }

**非递归实现**：对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。显式用栈，是基于循环实现的，代码的鲁棒性要更好一些。  
注意链表为空的情况。时间复杂度为O（n）。

/**
     * 6. 从尾到头打印单链表
     * 对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。
     * 显式用栈，是基于循环实现的，代码的鲁棒性要更好一些。
     * 注意链表为空的情况。时间复杂度为O（n）
     * @param head 链表头结点
     */
    public static void reversePrintByStack(ListNode head) {
        if (head == null) {
            return;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head != null) { // 将链表元素压入栈中
            stack.add(head);
            head = head.next;
        }
        while (!stack.isEmpty()) { // 将链表元素出栈打印
            System.out.print(stack.pop().val + "->");
        }
    }

##### 7. 判断单链表是否有环 #####

这里也是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。因此，我们用两个指针去遍历：first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。  
时间复杂度为O (n)。

/**
     * 7. 判断单链表是否有环：
     * 这里也是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是永远走不到头的。
     * 因此，我们用两个指针去遍历：first指针每次走一步，second指针每次走两步，
     * 如果first指针和second指针相遇，说明有环。时间复杂度为O (n)。
     * @param head 链表头结点
     * @return 是否存在环
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode first = head; // 每次移动一步
        ListNode second = head; // 每次移动两步
        while (second != null && second.next != null) { // 判断空指针
            first = first.next;
            second = second.next.next;
            if (first == second) {
                return true;
            }
        }
        return false;
    }

##### 8. 取出有环链表中环的长度 #####

思路：环的长度即为从开始到相遇处first走的步数。  
![环的长度][SouthEast]

/**
     * 8. 取出有环链表中，环的长度：从开始到相遇处first走的步数
     * @param head 链表头结点
     * @return 环的长度
     */
    public static int getCycleLength(ListNode head){
        if (head == null || head.next == null) {
            return 0;
        }
        int length = 0; // 环的长度
        ListNode first = head; // 每次移动一步
        ListNode second = head; // 每次移动两步
        while (second != null && second.next != null) { // 判断空指针
            first = first.next;
            second = second.next.next;
            length++;
            if (first == second) {
                return length;
            }
        }
        return 0;
    }

##### 9. 有环单链表中，取出环的起始点 #####

思路：从相遇点开始，设置一个节点从头开始，然后最终相遇的节点就是环的起始点。由上图中的a=c可知。

/**
     * 9、单链表中，取出环的起始点：从相遇点开始，设置一个节点从头开始，然后最终相遇的节点就是环的起始点。
     * @param head 链表头结点
     * @return 链表中环的起始节点
     */
    public static ListNode getCycleStart(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode first = head; // 每次移动一步
        ListNode second = head; // 每次移动两步
        while (second != null && second.next != null) { // 判断空指针
            first = first.next;
            second = second.next.next;
            if (first == second) {
                ListNode temp = head;
                while (temp != second) {
                    temp = temp.next;
                    second = second.next;
                }
                return second;
            }
        }
        return null;
    }

##### 10. 判断两个单链表相交的第一个交点。 剑指offer，题37。 #####

思路：先遍历两个链表得到长度差，让长的链表先走长度差步，然后再同时走相遇的第一个节点就是返回结果。

/**
     * 10、判断两个单链表相交的第一个交点。 剑指offer，题37。
     * 先遍历两个链表得到长度差，让长的链表先走长度差步，然后再同时走相遇的第一个节点就是返回结果。
     * 时间复杂度为：O(m+n)
     * @param head1 链表1头结点
     * @param head2 链表2头结点
     * @return 相交的第一个节点
     */
    public static ListNode meetNode(ListNode head1, ListNode head2){
        if (head1 == null || head2 == null) {
            return null;
        }
        int len1 = 0;
        int len2 = 0;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while (temp1 != null) {
            len1++;
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            len2++;
            temp2 = temp2.next;
        }
        int diff = Math.abs(len1 - len2);
        ListNode longHead = head1;
        ListNode shortHead = head2;
        if (len1 < len2) {
            longHead = head2;
            shortHead = head1;
        }
        for (int i = 0; i < diff; i++) {
            longHead = longHead.next;
        }
        while (longHead != null && shortHead != null && longHead != shortHead) {
            longHead = longHead.next;
            shortHead = shortHead.next;
        }
        return longHead;
    }

##### 11. 以 k 个节点为段，反转单链表。 #####

Reverse Nodes in k\_Group，Leetcode上的算法题，第5题的高级变种

/**
     * 11、以 k 个节点为段，反转单链表。
     * Reverse Nodes in k_Group，Leetcode上的算法题，第6题的高级变种
     * @param head 链表头结点
     * @param k 每k个节点反转
     * @return 反转后的链表头
     */
    public static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode curr = null;
        int count = 0;
        while (curr != null && count != k) { // find the k+1 node
            curr = curr.next;
            count++;
        }
        if (count == k) { // if k+1 node is found
            curr = reverseKGroup2(curr, k); // reverse list with k+1 node as head
            // head - head-pointer to direct part,
            // curr - head-pointer to reversed part;
            while (count-- > 0) { // reverse current k-group
                ListNode tmp = head.next; // tmp - next head in direct part
                head.next = curr; // preappending "direct" head to the reversed list
                curr = head; // move head of reversed part to a new node
                head = tmp; // move "direct" head to the next node in direct part
            }
            head = curr;
        }
        return head;
    }

[SouthEast]: /images/20220601/db96823670b3420b9e8818b51b3a4851.png