链表浅析及常用题目详解（链表反转，删除和环形链表等）

喜欢ヅ旅行 2022-11-03 00:42 141阅读 0赞

链表是物理存储单元上**非连续**的、**非顺序**的存储结构，它是由一个个结点，通过指针来联系起来的，其中每个结点包括数据和指针，如下图中单链表的表示。

![20210225213322289.png][]

文中统一使用以下单链表的定义：

public class Node {
        //节点next引用
        public Node next;
    
        //节点的数值域
        public int val;
    
        public Node() {
    
        }
    
        public Node(int val) {
            this.val = val;
        }
    }

链表的表示，头结点即表示数据结点，如下表示方法。

![20210225215558411.png][]

头结点使用**哨兵**节点，如下表示方法。

![20210225215740859.png][]

定义哨兵节点的好处，我们看看如果不定义哨兵节点，在链表尾部添加节点时操作。我们可以看到，对于每一个节点的加入，都需要判断head是否为空，其实只有第一个元素加入列表时这样的判断才是有意义的，后续的元素都是多此一举，还增加了额外的开销，而且不就是往末尾加一个元素吗？咋还有if else？，我们接下来看看有哨兵节点时addNode是怎么样的？

public void addNode(int val) {
            //如果头结点为空，则创建头结点
            if (head == null) {
                head = new Node(val);
            } else {
                //不为空时依次向后找到根节点，在根节点的后面执行插入
                Node tmp = head;
                while (tmp.next != null) {
                    tmp = tmp.next;
                }
                tmp.next = new Node(val);
            }
        }

有哨兵节点时。有没有很简单？而且插入时还省去了额外的空判断。后续都基于有哨兵头结点的情况来进行说明。

public class ListNode {
        //头结点，哨兵节点
        Node head = new Node();
    
        public ListNode() {
    
        }
    
        /**
         * 尾插法插入节点
         *
         * @param val
         */
        public void addNode(int val) {
            //找到根节点
            Node tmp = head;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = new Node(val);
        }
    }

接下来我们看下**头插法插入节点**，即每一次都在头部进行插入。如下图所以，要 插入节点 1。假如新加入的节点定义为newNode

![20210225230341932.png][]

（1）先执行newNode.next = head.next;

![20210225230600256.png][]

（2）执行head.next = newNode;

![20210225231556883.png][]

综上所述，头插法的代码如下。

/**
         * 头插法
         *
         * @param val
         */
        public void headInsert(int val) {
            //待插入的节点
            Node newNode = new Node(val);
            //code-1
            newNode.next = head.next;
            //code-2
            head.next = newNode;
        }

上述代码中 code-1 和 code-2处的代码能交换位置吗？答案是肯定不行的如果先执行 code-2，即先执行head.next =newNode，会导致后续节点丢失。如下图。所以写链表相关的题目时一定得注意节点丢失的情况。必要时可以借助画图来辅助理解，当图划出来时，问题自然就清晰明了了。

![20210225231424945.png][]

**删除给定节点**。如下图，如果我们要删除 值为 1 的节点（node）。需要找到 待 删除节点的前一个结点（preNode），然后执行preNode.next = node.next 和 node.next = null 即可。

![20210225234355656.png][]

但是有没有更快的办法呢？如果node.next = null，表示是尾结点，那没得办法，只能找到node节点的前一个结点，如果node.next 节点不为空，表示node.next 节点 不是尾结点，那还有更快的办法。分析如下。如果要删除值为 1 的节点 node。

![20210225235108897.png][]

我们可以把node.next.val 的值 设置给node.val，如下图。

![20210225235246990.png][]

然后此时问题就相当于转换为删除node.next节点，此时完全不需要遍历找到 待删除结点node.next 的前一个节点，因为node本就是node.next的前一个结点。经分析代码如下。

/**
         * 删除给定节点
         *
         * @param node 给定的节点，假设节点一定存在于链表中
         */
        public void deleteNode(Node node) {
            //表示node是尾结点
            if (node.next == null) {
                Node tmp = head;
                while (tmp.next != node) {
                    tmp = tmp.next;
                }
                // 找到尾结点的前继结点，把尾结点删除
                tmp.next = null;
            } else {
                //获取node的next节点
                Node nodeNext = node.next;
    
                // 将删除结点的后继结点的值赋给被删除结点
                node.val = nodeNext.val;
    
                //问题转换为删除nodeNext结点
                node.next = nodeNext.next;
    
                //删除node.next节点
                nodeNext.next = null;
            }
        }

这种删除的是不是很巧妙？时间复杂度是O(1)

**接下来我们看LeetCode上的题目，返回倒数第k个结点，此处假设k是有效的。如下链表。若 k = 2，则返回结点 4 。**

![2021022722193559.png][]

如果我们要求正数的第k个结点，那比较好处理，倒数的第k个结点就稍微比较麻烦了。有如下几个方向可以考虑

1、维护一个表示链表节点数量的属性length，则倒数第k，就可以转换为正数第length-k+1。

public class ListNode {
        //表示节点数量
        int length = 0;
    
        //头结点，哨兵节点
        Node head = new Node();
    
        public ListNode() {
    
        }
        //省略部分代码
    }

2、遍历两遍，第一遍获取获取链表的节点数量length，然后又转换为和方法一一样的处理办法。

3、那能否一遍搞定？双指针（快慢指针）出场。其实我们可以分析下，如果我们定义一个指针slow指向倒数第k个结点，指针fast指向倒数第一个结点（尾结点），此处我们假设k为2，看下什么情况，如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

发现没，slow再走 k-1 步就可以与fast相遇了，那如果slow 和 fast同时指向头结点，如果fast先走 k-1 步，然后slow 和 fast再同时走，当fast走到尾结点时，slow指向的节点即为倒数第k个结点。

（1）首先定义两个节点分别指向第一个有效节点（即排除哨兵节点）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

（2）fast节点先走k-1步（此处假设k为2），如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2][]

（3）然后slow 和 fast同步走，当fast走到结尾时，slow节点即为倒数第k个结点，如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

经上面分析，代码如下。

public Node kthToLast(int k) {
            //fast 和 slow 节点指向第一个结点
            Node fast = head.next;
            Node slow = head.next;
            //节点fast 走 k -1 步
            while (k > 1 && fast != null) {
                fast = fast.next;
                k--;
            }
            //fast 和 slow节点同步走，直到fast节点走到尾结点
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

时间复杂度为O（n），空间复杂度为O（1）。

接下来看下链表中一个比较经典的问题，**链表反转。**

翻转前：

![20210228124524353.png][]

翻转后

![20210228124614624.png][]

其实这个题目本身还是比较好理解的。但是处理起来还是稍微有点点麻烦。但是只要想通逻辑就比较简单了。接下来从递归和迭代两个方面处理这个问题。

1、基于递归的解决方案

我们可以看下，如果除第一个元素外其他都已经翻转了，那直接把指针改一下就好。其实对于后续的每一个元素都是类似的，所以可以定义一个递归函数。

![20210228162955312.png][]

递归函数：

递归终止条件：如果只有一个元素，如元素5时，直接返回即可。

![20210228165748669.png][]

最终的代码如下

/**
         * 翻转链表
         *
         * @return
         */
        public void reverseList() {
            Node node = reverseList(head.next);
            head.next = node;
        }
    
        /**
         * 翻转链表
         *
         * @param node
         * @return
         */
        private Node reverseList(Node node) {
            if (node.next == null) {
                return node;
            }
            Node newHead = reverseList(node.next);
            node.next.next = node;
            //避免形成回路
            node.next = null;
            return newHead;
        }

2、基于迭代的解决方案：还是使用双指针解决。我们可以看下以下链表。

![20210228174515696.png][]

（1）如果执行fast.next = slow 时会出现什么情况？如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3][]

（2）发现没，fast指针指向的节点与后续的节点断开了，所以我们执行fast.next = slow 时要先使用一个指针nextNode 把 关联关系记录下来，同时需要执行 slow.next = null，否则会形成环，如上图。所以修改后效果如下如。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4][]

（3）接着执行slow = fast 和 fast = nextNode，执行后如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5][]

再接着执行（2），直到fast 为空，如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6][]

此时执行head.next = slow 即可完成整个链表的交换。经上面分析，代码如下，结合代码和图，应该比较好理解：

public void reverseList() {
            Node slow = head.next;
            //说明是空链表
            if (slow == null) return;
            Node fast = head.next.next;
    
            //需要执行slow.next = null,避免形成环
            slow.next = null;
            while (fast != null) {
                Node nextNode = fast.next;
                //fast指向slow
                fast.next = slow;
                //slow 和 fast 后移
                slow = fast;
                fast = nextNode;
            }
            //最终执行head.next = slow 即可
            head.next = slow;
        }

我们接下来再来看个题目，**获取链表的中间节点**，如果链表有两个中间节点，即链表个数为偶数时返回第二个节点。如下图所示，第一条链表节点数量为奇数，所以直接返回中间节点3，第二条链表，节点个数为偶数个，中间节点为2 和 3 ，返回第二个即 节点3。

![20210228224230313.png][]

其实这个问题，还是可以使用双指针解决，比较巧妙。如下图，假设一段路程长度为L，有甲 乙 两个人从起点一起出发，假设甲的的速度为 v ，乙的行走速度为 2v，则乙走到终点时，甲刚好走到一半。其实这个题目本身也是类似的，我们可以定义两个节点，一个为slow每次走一步，一个为fast一次走两步，这时fast走到终点时，slow大概就指向中间位置。但是节点个数为奇数时 和 节点个数为偶数时边界条件稍微有点点区别。下面单独分析下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7][]

如果节点个数为奇数时。起始时slow 和 fast同时从起点出发，终止条件是fast.next = null。

![20210228225946711.png][]

如果节点个数为偶数时，起始时slow 和 fast同时从起点出发，当节点走到下面这种情况时，起始还不满足我们的要求，因为有两个中间节点时我们需要的是第二个。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8][]

再走一步看看，如下图，其实终止条件就是fast == null

![20210228230436697.png][]

经过上面的分析，代码如下。

public Node middleNode() {
            //起始时slow和fast指向起始节点，此处head是哨兵节点
            Node slow = head.next;
            Node fast = head.next;
    
            //对应奇偶的终止条件
            while (fast != null && fast.next != null) {
                //slow走一步，fast走两步
                slow = slow.next;
                fast = fast.next.next;
            }
            //最终slow指向的位置就是我们需要的节点
            return slow;
        }

判断链表是否有环，见博文[环形链表][Link 1]

[20210225213322289.png]: /images/20221024/adb7bb24937740eb8d4dd4133060ab72.png
[20210225215558411.png]: /images/20221024/af50032c61bb4d23bb115618b99e52b8.png
[20210225215740859.png]: /images/20221024/f27afcf013d44eeebce7aeaee68e8067.png
[20210225230341932.png]: /images/20221024/ecef3cfa191f418ebcfb3e7fd259c0ac.png
[20210225230600256.png]: /images/20221024/97cf856dd1ce47189634d6a179bc6a55.png
[20210225231556883.png]: /images/20221024/6e350d4ed7b24b3895683ee22b92e265.png
[20210225231424945.png]: /images/20221024/c2e70e3adcf14359a8557c958434ed1a.png
[20210225234355656.png]: /images/20221024/f3a795a385be42c6a0ccaaa3c598aea1.png
[20210225235108897.png]: /images/20221024/dc6b4beb4deb48c08f0ef04c26117107.png
[20210225235246990.png]: /images/20221024/2cdfa0fbab5848149805f99117104127.png
[2021022722193559.png]: /images/20221024/1c5d33c3a59940ae99ff917f8256cefa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20221024/0cb2e6cd0bcb436eb6c14de0cbecfec8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20221024/6d27eb9f395f4f9597cc8f88ae987000.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2]: /images/20221024/796f05310a1b496fb04cc748b66a4574.png
[20210228124524353.png]: /images/20221024/e3483aac59e9476fa68642e872afeeca.png
[20210228124614624.png]: /images/20221024/9f1c8965e2fd4c12b698ee8cb84288a7.png
[20210228162955312.png]: /images/20221024/a271386dc7414ba5bb4cdd4f95ba12b2.png
[20210228165748669.png]: /images/20221024/f2df7b6c5aca490395a6aeca4be97461.png
[20210228174515696.png]: /images/20221024/39132cfb4fed4ca3960f425be7ea1a74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3]: /images/20221024/9187dfbce410419bad0d62adabc16383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4]: /images/20221024/3423745cfb9a4fc1a8a52df6d6231cc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5]: /images/20221024/374e2745c54840ef8ec6edc827d8fbdb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6]: /images/20221024/da560cb57e664a6b92867b0430d8fb2f.png
[20210228224230313.png]: /images/20221024/0ad4b1b22f3c458c9f7ceb597b99bec0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7]: /images/20221024/5c11f35a2dd34e5da63645d817bf070a.png
[20210228225946711.png]: /images/20221024/1ba0b3f3c0b74547a9f039748883e848.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8]: /images/20221024/c0d65a8e8bbf4fedac37b52a28d23d98.png
[20210228230436697.png]: /images/20221024/afef162ae98e4d1ab6c1d7591a6fc18d.png
[Link 1]: https://blog.csdn.net/ycb1914845451/article/details/109783908?spm=1001.2014.3001.5501