• 《算法系列》之链表

    简介

       我们平时会发现如果一道题如果涉及数据结构，那么他的算法思路一般相对其它同等难度的题要简单，其实链表也一样，纯链表的题也不会特别难。了解了一些套路之后，做题方法也是有迹可寻，我们可以适当记一些模板，这样可以加快我们解题的速度，比如如何寻找中点，用虚拟节点或递归法反转链表等，其中递归是链表篇的重点，其实也整个刷题生涯中的重点，链表中的递归，回溯中的递归，二叉树和图中的递归等等，所以这里也会讲一下递归的书写模板，要重点学习。

    理论基础

      链表是一种线性存储结构，采用的是链式存储。可以采用连续的存储空间，也可以采用零散的非连续存储空间。 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表示意图如下：
    请添加图片描述
       除了以上这种单链表以外，还有双向链表和循环链表。在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点指向前一个结点，构成一个链表，就产生了双向链表的概念了。即每个节点都有两个指针。双向链表示意图如下：

    请添加图片描述
    循环链表其实也好理解，就是首尾节点连接在一起了罢了，我们平时写链表代码时，如非必要，要注意循环链表的产生，否则可能会导致CPU空转，出现致命BUG，循环链表示意图如下：
    请添加图片描述

    链表的特点
    • 是一种线性存储结构。
    • 节点值包含两部分，分别为数据域和指针域。
    • 可以采用零散的存储空间。
    • 和数组相比，内存消耗更大，主要需要多存一个指针域。
    • 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。
    • 和数组比，无固定长度，理论上来讲，只要内存没爆，能一直存。
    • 线性链表还可分为单链表，双向链表，循环链表等。
    • 链表节点的增加一般有头插入法和尾插入法两种。

    链表类的定义：

    public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    解题方式

       解链表的题，一定要会两招，一招是递归，一招是迭代法。其中递归的写法可以分成三步走：

    • 一、明确函数功能： 要清楚你写这个函数是想要做什么。

    • 二、寻找递归出口： 递归一定要有结束条件，不然会永远递归下去，禁止套娃。

    • 三、找出递推关系： 开始实现递归，一步一步递推出最终结果。
      递归方式主要在链表反转时，或者需要从后往前操作链表时，经常用到，写递归函数时，一定要明确递推关系和递归出口，否则不可能写好递归的。至于迭代法，其实不过就是写循环，一般比递归要好理解一些，代码也更好写，但有的题不能直接看出来用迭代法，但请相信：所有的递归都可以用循环来写。接下来看一下递归和迭代的模板：

      // 递归模板
class Solution {
    public BBB AAA(ListNode head) {
        return helper(入参);
    }

    private BBB helper(入参) {
        if (终止条件) {
            return xxx;
        }
        // 函数功能
        return helper(参数); # 递归调用
    }
}

// 迭代模板
... 其实就是 for 或 while 循环 ...
	for(...){
		... ...
	}

	while(...){
		... ...
	}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24

      下面以反转链表这题经典题，来展示这两种方法。

      // 递归法反转链表
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

// 迭代法反转链表
class Solution {
    public ListNode reverseList(ListNode head) {
        // 申请新虚拟节点
        ListNode dummy = new ListNode(0);
        ListNode p = dummy, cur = head;
        while(cur != null){
            // 从head摘下一个头
            ListNode t = cur;
            cur = cur.next;     // cur移到下一个
            t.next = p.next;    // 头插法插入，依次反转
            p.next = t;
        }
        return dummy.next;
    }
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36

       以上迭代法的书写方式，也可以叫做虚拟头节点法，相当于递归来说，更易于我们理解。链表的题，有时申请一个虚拟头节点，题解就会豁然开朗。

    解题心得

    • 只要弄清链表的特性，单纯的链表题一般也不难。
    • 一定要学会几种反转链表的方式，很重要。
    • 递归一定要好好学习，无论是链表题，还是之后的题，都会经常用到，最好能理解并默写模板。
    • 寻找链表中点，只需要用双指针，Slow前行一步，Fast前行两步，Fast到底，Slow就是中间节点了。
    • 在leetcode中通常链表已经定义好了，但我们平时也要注意链表类的定义怎么写，因为面试时，是不会有人给你定义的，这些都需要你自己写。

    算法题目

    2. 两数相加

    在这里插入图片描述
    题目解析：将两链表直接相加，要注意进位（carry）的处理，这里可以用虚拟头节点来处理链表，会更方便。
    代码如下：

    /**
 * Definition for singly-linked list.
 * public caass ListNode {
 *     int bal;
 *     ListNodeint val; next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 
/**
 * 链表
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 声明一个虚拟头节点
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        // 只要有一个链表不为空，则需继续相加
        while(l1 != null || l2 != null){
            int a = (l1 != null) ? l1.val : 0;
            int b = (l2 != null) ? l2.val : 0;
            int sum = carry + a + b;
            // 无进位，则carry为零
            carry = sum / 10;
            // 节点值为个位数数值
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if(l1 != null ) l1 = l1.next;
            if(l2 != null ) l2 = l2.next;
        }
        // 若最后有进位，则新加一个节点
        if(carry > 0){
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

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

    在这里插入图片描述
    题目解析：递归整个链表，然后按两两相交的规则，重新生成新链表。
    代码如下：

    /**
 * 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 swapPairs(ListNode head) {
        return swap(head);
    }

    public ListNode swap(ListNode head){
        
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode tampA = head;
        ListNode tampB = head.next.next;
        // 按新链表的生成顺序，完成代码书写，更便于理解
        head = head.next;
        head.next = tampA;
        head.next.next = swap(tampB);
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    25. K 个一组翻转链表

    在这里插入图片描述
    题目解析：这里需要双重递归，每过K个节点，再执行递归进行链表反转这K个节点。
    代码如下：

    /**
 * 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 reverseKGroup(ListNode head, int k) {
        // 新的head
        ListNode newHead = head;
        // 运行至该节点
        ListNode tempA = head;
        for (int i = 0; i < k; i++) {
            if (tempA == null) {
                return head;
            }
            if (i == k - 1) {
                newHead = tempA;
            }
            tempA = tempA.next;
        }
        // 反转后的最后一个节点
        ListNode tempB = reverse(head, k);
        // 当前段最后一个节点与下一段开头相连
        tempB.next = reverseKGroup(tempA, k);
        return newHead;
    }

    /**
     * 用递归反转链表
     */
    public ListNode reverse(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        ListNode newHead = reverse(head.next, --k);
        newHead.next = head;
        return newHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    83. 删除排序链表中的重复元素

    在这里插入图片描述
    题目解析：直接遍历全链表，有重复删除即可。
    代码如下：

    /**
 * 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 deleteDuplicates(ListNode head) {
        ListNode res = head;
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    92. 反转链表 II

    在这里插入图片描述
    题目解析：用递归反转指定范围里的节点，再连接进主链表即可。
    代码如下：

    /**
 * 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 {

    ListNode successor = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == 1) {
            return helper(head, right);
        }

        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    public ListNode helper(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }

        ListNode last = helper(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    155. 最小栈

    在这里插入图片描述

    题目解析：用链表，每个节点存储时，把该节点情况下最小值也存进去即可。
    代码如下：

    /**
 * 链表
 */
class MinStack {
    private Node head;
    
    public void push(int x) {
        if(head == null) 
            head = new Node(x, x);
        else 
            head = new Node(x, Math.min(x, head.min), head);
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
    
    private class Node {
        int val;
        int min;
        Node next;
        
        private Node(int val, int min) {
            this(val, min, null);
        }
        
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    203. 移除链表元素

    在这里插入图片描述
    题目解析：虚拟头节点，用虚拟头节点的好处是，防止第一个节点也是删除的节点的情况，且方便返回头节点。

    代码如下：

    /**
 * 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) {
        ListNode header = new ListNode(-1);
        header.next = head;
        ListNode cur = header;
        while(cur.next != null){
            // 当前节点下一节点为删除节点时，直接删除掉下一节点
            if(cur.next.val == val ){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return header.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    206. 反转链表

    在这里插入图片描述
    题目解析：虚拟头节点，用虚拟头节点方便返回头节点。
    代码如下：

    /**
 * 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 null;
        }

        ListNode dummyHead = new ListNode(-1);
        while(head != null){
            ListNode temp = dummyHead.next;
            dummyHead.next = new ListNode(head.val);
            dummyHead.next.next = temp;
            head = head.next;
        }
        return dummyHead.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    237. 删除链表中的节点

    在这里插入图片描述
    题目解析：依次用后一节点的值代替当前节点的值。
    代码如下：

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/**
 * 链表
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 今当前节点值为下一节点值
        node.val = node.next.val;
        // 申请下一节点
        ListNode nextNode = node.next;
        // 判断依次替换之后的节点
        while (nextNode.next != null) {
            nextNode.val = nextNode.next.val;
            node = nextNode;
            nextNode = nextNode.next;
        }
        // 删除最后一个节点
        node.next = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    回到首页

    刷 leetcode 500+ 题的一些感受

    下一篇

    [xxxxx]

  • 相关阅读:
    三维重建_使用OpenMVG/OpenMVS重建场景
    Future
    使用react-draggable和react-resizable实现Ant Design Modal的拖动和拖拽改变宽度
    同一台Linux同时安装MYSQL5.7和MYSQL8（第一篇）
    2022Java 大厂高频面试题，原理 + 实战 + 视频 + 源码
    log4cplus最新介绍、详细编译过程及使用(最全面)
    InnoDB 是如何解决幻读的
    解答：EasyDSS视频点播时音频是否可以设置为默认开启？
    配置CentOS
    八股文学习三（jvm+线程池+锁）
  • 原文地址：https://blog.csdn.net/qq_22136439/article/details/122231911