刷题|和链表相关的题目思路分析与总结

待我称王封你为后i 2021-11-10 13:38 215阅读 0赞

### 刷题|和链表相关的题目思路分析与总结 ###

*  1 数据结构
 *   *  1.1 单链表
     *  1.2 循环链表
     *  1.3 双向链表
     *  1.4 链表和数组对比
 *  2 链表相关题目
 *   *  2.1 链表编程技巧
     *   *  1）需要移动指针时，新建一个指针来移动
         *  2） 不要弄丢指针，注意指针的操作顺序
         *  3） 利用哨兵机制
         *  4）关注边界条件处理
     *  2.2 链表题目类型
     *  2.3 LeetCode链表相关的题目
     *   *  206. 反转链表
         *  2. 两数相加
         *  24. 两两交换链表中的节点
         *  142. 环形链表
 *  参考资料

# 1 数据结构 #

## 1.1 单链表 ##

**链表通过指针将一组零散的内存块串联在一起。**

*  把内存块称为链表的“结点”。
 *  为了将所有的结点串联起来，每个链表的结点除了**存储数据**之外，还需要记录链上的**下一个结点地址**。
 *  把这个记录下个结点地址的指针叫做**后继指针next**。

看了上面的描述最基本的单链表的数据结构就可以写出来了：

// 单链表
     public class ListNode {
        
         int val;
         ListNode next;
         ListNode(int x) {
         val = x; }
    }

**在单链表中，有两个结点比较特殊：**

*  头结点：即第一个结点，用来记录链表的基地址。有了它，就可以遍历得到整条链表。
 *  尾结点：即最后一个结点，其next指针不是指向下一个节点，而是指向一个空地址null，表示这是链表上最后一个结点。

**与数组一样，链表也支持数据的查找、插入和删除操作。**

*  链表的插入和删除操作只需要考虑相邻结点的指针变化，而无需像数组那样为了保证内存的连续性而搬移结点，其对应的时间复杂度为O(1)。
 *  但是链表不支持随机访问。链表中的数据并非连续存储，故无法像数组那样根据基地址和下标可直接计算出对应内存地址。其只能根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

## 1.2 循环链表 ##

循环链表是一种特殊的单链表。单链表的尾结点next指针指向null，而循环链表中**尾结点next指针指向头结点**。即像一个环一样首尾相连。

循环链表相比单链表的优点在于：

*  从**链尾到链头比较方便**。
 *  当要处理的数据具有**环形结构特点**时，特别适合采用循环链表。比如约瑟夫环问题。

## 1.3 双向链表 ##

双向链表支持两个方向，每个结点不止有一个后**继指针next**指向后面的结点，还有一个**前驱指针prev**指向前面的结点。数据结构如下所示：

// 双向链表
     public class ListNode {
        
         int val;
         ListNode next;
         ListNode prev;
         ListNode(int x) {
         val = x; }
    }

**双向链表和单链表相比：**

*  双向链表需要额外的空间存储前驱结点的地址，所以如果存储同样多数据，双向链表要比单链表占用更多内存空间。
 *  但是双向链表支持**O(1)复杂度找到前驱结点**，使得双向链表在某些情况下插入、删除等操作比单链表简单、高效。
 *  双向链表**按值查询**的效率也比单链表高。

在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表应用更加广泛。

**双向链表操作的时间复杂度分析：**

*  在实际开发中，从链表中删除一个数据无外乎下面两种情况：  
    – **删除结点中“值等于某个给定值”的结点**  
    不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个一次遍历对比，直到找到值等于给定值的结点，然后再通过我指针操作将其删除。  
    在这个过程中虽然删除操作的时间复杂度是O(1)，但遍历查找的时间复杂度是O(n)。故删除值等于给定值的结点对应的链表操作的时间复杂度为O(n)。  
    – **删除给定指针指向的结点**  
    在这种情况中，已经找到了要删除的结点，删除某个结点q需要知道其前驱结点，单链表只能通过从头遍历获得其前驱结点，故时间复杂度为O(n)。但双向链表由于保存了前驱结点，故时间复杂度为O(1)。
 *  对一个有序链表，双向链表的按值查询的效率也比单链表高。因为我们可以记录上次查找的位置p，利用二分查找，决定向前还是向后查找。平均只需要查找一半的数据。

## 1.4 链表和数组对比 ##

**从时间复杂度的人角度：**

*  链表：插入删除O(n) 随机访问O(n)
 *  数组：插入删除O(n) 随机访问O(1)

**从利用缓存的角度：**

*  数组在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。
 *  而链表在内存中并不是连续存储，对CPU缓存不友好，没办法有效预读。

**从空间分配角度：**

*  数组的缺点是大小是固定的，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配，导致out of memory。如果数组声明过小，可能会不够用，导致后续需要扩容，而扩容很费时（支持动态扩容的数组不过是把扩容在内部封装了，扩容一样耗时）。
 *  链表本身没有大小限制，天然支持动态扩容。对链表频繁插入删除，会导致频繁的内存申请和释放，容易造成内存碎片。（在Java中会导致频繁GC）。

在实际开发中，要针对不同类型项目的具体情况，进行权衡。

*  对内存使用要求苛刻，追求性能的更适合数组。

# 2 链表相关题目 #

和链表相关的题目一般需要正确处理指针操作，有时会指指着把元素丢了（链断了）。而链表中由于有node.next，甚至node.next.next的这样语句的存在，常常需要判别node是否为null，node.next是否为null，在这个过程中头结点和尾结点常常需要特殊考虑，导致需要为其编写更多的代码，容易考虑不周出现问题。下面介绍几个链表编程技巧。

## 2.1 链表编程技巧 ##

### 1）需要移动指针时，新建一个指针来移动 ###

链表编程的题目，一般参数或传入一个Node head，让你完成相关操作，然后返回更新后的链表。注意，链表的移动过程需要不断改变当下节点位置，所以不要用原始指针移动，要新建一个指针来移动，不然后面找不到链表头了。如下：

public Node test(Node head) {
        
    	// 新建一个结点用来移动
    	Node help = head;
    	while(help != null) {
        
    		help = help.next;
    	}
    	return head;
    }

### 2） 不要弄丢指针，注意指针的操作顺序 ###

指针操作不当，会导致断链，所以在处理的时候要头脑清醒，想想这样有没有问题。以下代码就有问题：

// 目的是把x插入链中（插入到p后面）
    p.next = x;
    x.next = p.next;

上面的代码在完成第一步后，p.next已经指向了x，而第二步让x.next指向自己，导致后面的链断了。所以我们在处理时，应该先处理x.next域。如下所示：

// 目的是把x插入链中（插入到p后面）
    x.next = p.next;
    p.next = x;

### 3） 利用哨兵机制 ###

在链表编程中，第一个结点需要特别关注，因为我们往往在循环过程中，需要使用这样的语句`head.next`，那自然地head不能为null，在编程中需要对head进行特别处理，就很麻烦，而且容易忘记。采用如下方法，可以简化编程：

// new 一个Node(0)作为链表头
    // 这样就不要特别考虑设置表头的问题
    // 直接 re.next就行
    Node re  = new Node(0);
    
    // 一些具体操作
    // ...
    
    // 返回的时候，从哨兵的下一个节点返回就行
    return re.next;

### 4）关注边界条件处理 ###

在编写链表代码时，要注意考虑以下几个边界条件：

*  链表为空
 *  链表只包含一个结点
 *  链表只包含两个节点
 *  头结点和尾结点

## 2.2 链表题目类型 ##

一般有如下几种题目：

1.  反转链表
2.  判断是否有环以及找到环入口
3.  删除倒数第k个结点
4.  合并两个/n个有序链表
5.  两个链表代表的数字相加

## 2.3 LeetCode链表相关的题目 ##

### 206. 反转链表 ###

反转一个单链表。

示例:  
输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

**思路分析：**

反转链表是链表解题中最常见和最基础的题目，需要考虑的点在于：

1.  边界处理，反转链表需要对node.next域进行操作，所以先考虑node如果为null，直接返回null；另外如果只有一个节点，即node.next为null，则不用反转，直接返回node。这两个情况综合起来就是返回node 。
2.  反转链表的过程中涉及pre、curr和next三种节点。pre初始化为null，curr初始化为head，目前的pre就是反转后链表的尾巴。所谓反转就是需要curr.next指向pre，所以处理过程中，为了能继续遍历下去，注意用一个临时节点保存next节点，不然执行了`curr.next = pre`以后，链就断了。
3.  最后返回的结点应该是pre，因为curr会多走一步，走到null。

题目说用两种方式写，递归的方式好像不太会，最先想到就是迭代，那就先写迭代吧：

public ListNode reverseList(ListNode head) {
        
            // head为null，或只有一个节点
            if(head == null || head.next == null)
                return head;
            ListNode pre = null;
            ListNode node = head;
            while(node != null){
        
                ListNode temp = node.next;
                node.next = pre;
                pre = node;
                node = temp;
            }
            return pre;
        }

递归写法如下，参考了别人的代码，我觉得好难理解啊，这个圈圈转不过来：

public ListNode reverseList(ListNode head) {
        
            if(head == null || head.next == null){
        
                return head;
            }
            
            ListNode node = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            
            return node;
        }

递归版本的解析如下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rhcmxpbmd3b29kMjAxMw_size_16_color_FFFFFF_t_70][]  
递归这里其实还没想明白，后面再IDE上调试一下看一下。

### 2. 两数相加 ###

给出 **两个** 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：  
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  
输出：7 -> 0 -> 8  
原因：342 + 465 = 807

**思路分析：**

整体还是很简单的，对应位置相加，考虑进位。需要考虑的点在于：

1.  链表长度如果一样的话，那就非常简单了，链表长度不一致也不难，只是需要对多出来的部分进行判断。
2.  返回一个新链表，所以要对头结点特殊考虑。
3.  别忘了最后可能还有进位。

先来看看我第一个写这个题写的代码有多丑(￢\_￢)：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            if(l1 == null && l1 == null)
                return null;
            if(l1 == null || l2 == null)
                return l1 == null ? l2: l1;
            
            // temp表示进位
            int temp = 0;
            ListNode head = new ListNode(-1);
            ListNode re = head;
            
            // 先处理低位长度相等的情况
            while(l1 != null && l2 != null){
        
                int newVal = (l1.val+l2.val+temp) % 10;
                head.next = new ListNode(newVal);
                temp = (l1.val+l2.val+temp) / 10;
                head = head.next;
                l1 = l1.next;
                l2 = l2.next;
                
            }
            if(l1 == null && l2 != null){
        
                while(l2 != null){
        
                    int newVal = (l2.val+temp) % 10;
                    head.next = new ListNode(newVal);
                    temp = (l2.val+temp) / 10;
                    head = head.next;
                    l2 = l2.next;
                }
            }else if(l1 != null && l2 == null){
        
                while(l1 != null){
        
                    int newVal = (l1.val+temp) % 10;
                    head.next = new ListNode(newVal);
                    temp = (l1.val+temp) / 10;
                    head = head.next;
                    l1 = l1.next;
                }
            } 
            if(temp != 0){
        
                head.next = new ListNode(temp);
            }
            return re.next;
        }

上面代码用到了前面提到的哨兵机制，并且保留了一个节点re，用哨兵节点去移动，最后返回re.next。思路没什么问题，就是对于长度不相等的处理导致代码太冗余了，相同逻辑的部分出现了三次。下面改进下写法，让代码看着清爽点：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            if(l1 == null && l1 == null)
                return null;
            if(l1 == null || l2 == null)
                return l1 == null ? l2: l1;
            
            // temp表示进位
            int temp = 0;
            // 哨兵
            ListNode head = new ListNode(-1);
            // 返回的节点
            ListNode re = head;
            
            // 当l1和l2都为空时结束
            // 这个写法把长度不同放一起考虑了
            while(l1 != null || l2 != null){
        
            	// 关键是要知道两个链表的每一位是什么
            	// 如果链表走完了，那就是0
                int lv1 = l1 == null ? 0: l1.val;
                int lv2 = l2 == null ? 0: l2.val;
                int newVal = (lv1+lv2+temp) % 10;
                head.next = new ListNode(newVal);
                temp = (lv1+lv2+temp) / 10;
                head = head.next;
                // 因为两个链表放在一起考虑了
                // 所以可能有一个先为null
                // next的时候要先判断是不是为空
                // 不然会出错的
                if(l1 != null)
                    l1 = l1.next;
                if(l2 != null)
                    l2 = l2.next;
                
            }
            // 注意最后还可能有进位
            if(temp != 0){
        
                head.next = new ListNode(temp);
            }
            return re.next;
        }

上面的代码把长度不同放在一个while里考虑，代码看起来清爽多了，但其实其比第一种写法多判断了很多次。比如说l1先走完了，l2还没走完。它在while里面还是会一遍又一遍的问l1你是不是走完了，l2你是不是走完了。而第一种写法显然不会，先处理长度相同的部分，然后谁没走完就走谁（一定有一个在while里先走完）。我pick第二种~

### 24. 两两交换链表中的节点 ###

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。  
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:  
给定 1->2->3->4, 你应该返回 2->1->4->3.

class Solution {
        
        // 法二 用传统递归的思想
        public ListNode swapPairs(ListNode head) {
        
            if(head == null || head.next == null)
                return head;
            // 辅助节点
            ListNode node = head;
            // 哨兵节点
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            ListNode pre = dummyHead;
            
            while(node != null && node.next != null) {
        
                ListNode temp = node.next;
                node.next = node.next.next;
                temp.next = node;
                pre.next = temp;
                pre = node;
                node = node.next;
            }
            return dummyHead.next;
        }
    }

class Solution {
        
        
        // 法一 递归 十分优雅
        public ListNode swapPairs(ListNode head) {
        
             // 1.找终止条件。 
             // 什么情况下递归终止？没得交换的时候，递归就终止了呗。
             // 因此当链表只剩一个节点或者没有节点的时候，自然递归就终止了。
             if(head == null || head.next == null)
                 return head;
             // 一共三个节点:head, next, swapPairs(next.next)
           	// 下面的任务便是交换这3个节点中的前两个节点
             ListNode next = head.next;
             head.next = swapPairs(next.next);
             next.next = head;
             // 根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
             return next;
         }
    }

### 142. 环形链表 ###

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：  
输入：head = \[3,2,0,-4\], pos = 1  
输出：tail connects to node index 1  
解释：链表中有一个环，其尾部连接到第二个节点。

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            if(head == null || head.next == null || head.next.next == null)
                return null;
            ListNode p1 = head;
            ListNode p2 = head;
            boolean flag = false;
            // 判断是否有环
            while(p1.next != null && p2.next != null && p2.next.next != null){
        
                p1 = p1.next;
                p2 = p2.next.next;
                if(p1 == p2){
        
                    flag = true;
                    break;
                }
                    
            }
            ListNode p = head;
            while(flag){
        
                if(p == p1){
        
                    return p;
                }
                p = p.next;
                p1 = p1.next;
            }
            return null;
        }
    }

# 参考资料 #

极客时间  
题解：  
https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rhcmxpbmd3b29kMjAxMw_size_16_color_FFFFFF_t_70]: /images/20211109/8acd22d6335d47219a8f214cc6ccc9af.png