• leetcode面试题之链表

    文章目录

    203. 移除链表元素

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

    链接：https://leetcode.cn/problems/remove-linked-list-elements/

    思路：单链表
    定义一个虚拟头结点，便于所有结点统一处理

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head; // 初始条件判断
        ListNode dummy = new ListNode(-1, head); // 创建虚拟头结点，方便后续统一处理
        ListNode pre = dummy, cur = head;
        while (cur != null) {
            if (cur.val == val) { // 找到值相同的节点，删除
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    206. 反转链表

    题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    链接：https://leetcode.cn/problems/reverse-linked-list/

    思路：双指针 pre cur temp

    public ListNode reverseList(ListNode head) {
         ListNode pre = null, cur = head, temp = null; // 初始化节点
         while (cur != null) {
             temp = cur.next; // 保存下一个节点
             // 翻转
             cur.next = pre;
             // 更新pre cur
             pre = cur;
             cur = temp;
         }
         return pre;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    707. 设计链表

    题目：单链表或双链表。单链表中的节点应该具有两个属性：val 和 next，双链表再加一个pre

    get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
    addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
    addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
    deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

    链接：https://leetcode.cn/problems/design-linked-list/

    思路：链表基本操作

    class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    ListNode head; // 虚拟头结点
    int size; // 链表长度

    // 初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) { // 初始条件判断
            return -1;
        }
        ListNode p = head;
        for (int i = 0; i <= index; i ++) { // 这里创建了一个虚拟头结点，所以查到的是index+1位置的节点
            p = p.next;
        }
        return p.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        // 初始条件判断
        if (index > size) return;
        if (index < 0) index = 0;
       
        size ++; 
        // 找插入位置的前驱节点
        ListNode pre = head;
        for (int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 插入
        ListNode p = new ListNode(val); // 待插入的新节点
        p.next = pre.next;
        pre.next = p;
    }
    
    public void deleteAtIndex(int index) {
        // 初始条件判断
        if (index < 0 || index >= size) return;

        size --;
        // 找删除位置的前驱结点
        ListNode pre = head;
        for (int i = 0; i < index; i ++) {
            pre = pre.next;
        }
        // 删除
        pre.next = pre.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

    • 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
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

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

    题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

    链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

    思路：记住三个步骤

    public ListNode swapPairs(ListNode head) {
        // 创建虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        // 遍历：保证当前节点和下一个节点都不为空
        while (pre.next != null && pre.next.next != null) {
            ListNode temp = head.next.next; // 记录next
            pre.next = head.next; // 步骤1
            head.next.next = head; // 步骤2
            head.next = temp; // 步骤3
            // 继续前进
            pre = head;
            head = head.next;
        }
        return dummy.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    19. 删除链表的倒数第 N 个结点

    题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

    思路：双指针

    1. 定义一个虚拟头结点
    2. 定义快慢指针，快指针先走n+1步
    3. 快慢指针一起走，快指针走到尾时，慢指针刚好走到要删除位置的前驱结点
    4. 删除n位置的节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义快慢指针
        ListNode fast = dummy, slow = dummy;
        // 快指针先走n+1步，然后快慢指针一起走，当快指针走到尾时，慢指针走到要删除指针的前一个位置
        for (int i = 0; i <= n; i ++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode pre = slow;
        // 删除第n个位置的节点
        pre.next = slow.next.next; 
        return dummy.next;
    }

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

    面试题 02.07. 链表相交

    题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

    链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

    思路：双指针
    A B两个指针同时走，走到尾还没相交，则指向另一个链表继续走，直到相交

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        // A B两个指针同时走，走到尾还没相交，则指向另一个链表继续走，直到相交
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    142. 环形链表 II

    题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null；有环则返回环的入口节点

    链接：https://leetcode.cn/problems/linked-list-cycle-ii/

    思路：快慢指针
    1.判断是否有环
    2.如果有环再找环的入口节点
    （找环的入口看下面的推导思路）

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        // 先找相交点，快指针一次走两步，慢指针一次走一步
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 相遇，快指针回到头结点开始，慢指针继续在相遇点
            if (fast == slow) {
                fast = head;
                // 同时开始都每次走一步，相遇点即为环的入口点
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

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

    链表：环相关总结

    1、判断链表是否有环？

    快慢指针：快指针走两步，慢指针走一步，相交表示有环

    2、怎么找环的入口？

    在这里插入图片描述

    1、到达相遇点时，快慢指针走的步数

    慢指针：x+y ；快指针：x+y+n(y+z)

    2、公式推导：

    快指针一次走两步，慢指针一次走一步，所以：2*(x+y) =x+y+n(y+z)

    => x=n(y+z)-y => x = (n - 1) (y + z) + z

    3、最后，快指针从头结点出发，慢指针从相遇节点继续出发，每次都走一步，此时的相遇点即为环形入口点

    剑指 Offer 06. 从尾到头打印链表

    题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

    链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

    思路：

    1.先遍历一次，求得数组长度
    2.再遍历一次，用数组存储所有节点值（从尾部开始存储）
    注意：第二次遍历的条件

    public int[] reversePrint(ListNode head) {
        int n = 0;
        ListNode p = head;
        // 先遍历一遍，求得链表长度
        while (p != null) {
            p = p.next;
            n ++;
        }
        // 指针回到表头，再遍历一遍，将节点值存放到数组中，数组从尾开始遍历
        int[] res = new int[n];
        p = head;
        for (int i = n - 1; i >= 0; -- i) { // 注意遍历的条件
            res[i] = p.val;
            p = p.next;
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    剑指 Offer 35. 复杂链表的复制

    题目：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null

    链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof

    思路：哈希表 HashMap

    1. 第一次遍历，根据oldNode值创建newNode，建立map
    2. 第二次遍历，缺点next、random的指针指向
    public Node copyRandomList(Node head) {
        // 初始判空条件
        if (head == null) return null;
        Node node = head;
        // map(node, newNode)
        Map<Node, Node> map = new HashMap<>();
        // 遍历，生成map
        while (node != null) {
            map.put(node, new Node(node.val));
            node = node.next;
        }
        // 遍历，处理next random指针
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next); // map.get(node)=newNode
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head); // 返回复制后的头结点
    }

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

    剑指 Offer 18. 删除链表的节点

    题目：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点
    返回删除后的链表的头节点。

    链接：https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/

    思路：

    1.建立虚拟头结点，使得所有节点操作一样
    2.head保存新的头结点
    3.遍历，找到要删除的节点，删除并结束循环
    4.最后没找到，返回头结点

    public ListNode deleteNode(ListNode head, int val) {
        // 创建虚拟头结点，使得所有节点操作方式一样
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 保存一下链表的头结点
        head = dummy;
        // 遍历
        while (dummy.next != null) {
            // 找到要删除的节点，删除并结束循环
            if (dummy.next.val == val) {
                dummy.next = dummy.next.next;
                return head.next;
            }
            dummy = dummy.next;
        }
        return head.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    剑指 Offer 25. 合并两个排序的链表

    题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

    链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

    思路：1. 同时遍历l1 l2，将较小的值放入l3
    2. 当有一个遍历完成，l3指向剩余的那个

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(-1), cur = l3;
        // 同时遍历l1 l2，将较小的值放入l3
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // l1或l2有一个遍历完成，将l3指向剩下的那个链表
        cur.next = l1 != null ? l1 : l2;
        return l3.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    剑指 Offer 22. 链表中倒数第k个节点

    题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

    链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

    思路：双指针

    1.创建虚拟头结点

    2.p1先走k步，p1 p2再一起走，当p1到尾结点时，p2刚好走到倒数第k位置的前驱结点

    public ListNode getKthFromEnd(ListNode head, int k) {
        // 创建虚拟头结点，使得所有节点操作一样
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义p1 p2两个指针，p1先走k步
        ListNode p1 = dummy, p2 = dummy;
        for (int i = 0; i < k; i ++) {
            p1 = p1.next;
        }
        // 当p2没到达尾结点时，p1 p2一起走
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 最后p2刚好走到倒数第k位置的前驱结点（画图）
        return p2.next;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    831.KMP字符串
    人工智能轨道交通行业周刊-第25期（2022.11.28-12.4）
    怎样克服上公开课的心里恐惧？
    FL Studio2024官方破解中文版本下载
    如何中断一个正在运行的线程？
    IBM X3650 M4服务器配置 并上线JavaWeb项目
    Redis基本知识
    VMware Workstation提示：另一个程序已锁定文件的一部分，进程无法访问，删除.lck文件夹和文件
    模拟电路（详细版）--放大电路的频率效应(RC电路)
    【子串】151. 反转字符串中的单词【中等】
  • 原文地址：https://blog.csdn.net/mys_mys/article/details/126680728