【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制

---

🐌个人主页： 🐌 叶落闲庭
💨我的专栏：💨
c语言
数据结构
javaEE
操作系统
Redis

石可破也，而不可夺坚；丹可磨也，而不可夺赤。

---

一、删除链表的倒数第 N 个结点

1.1 题目描述

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

---

---

---

1.2 思路分析

我的思路是先求出整个链表的长度，要删除倒数第n个节点，则将链表的长度减去n得到要删除的节点的前一个节点的索引，将链表长度减n+1得到要删除的节点的索引，定义两个指针，一个指针表示要删节点的前一个节点，另一个表示要删的节点，根据两个索引值对链表进行遍历，遍历索引值减1次就能得到索引对应的节点处，然后将要删节点的前一个节点的next指向要删的节点的next，完成倒数第n个节点的删除，当要删除的是第一个节点时（即删除倒数第链表长度个节点），直接改变头节点的位置即可。

1.3 代码演示

public ListNode removeNthFromEnd(ListNode head, int n) {
        //求出链表的长度
        int len = listLen(head);
        //如果是删除第一个节点，就是头删
        if(n == len) {
            head = head.next;
            return head;
        }
        //定义两个节点指针
        ListNode prev = head;
        ListNode del = head;
        //求出要删节点前的的节点位置
        int l = len - n;
        //求出要删除节点的位置
        int d = len - n + 1;
        //遍历链表找到这两个节点
        for(int i = 0;i < l - 1; i++) {
            prev = prev.next;
        }
        for(int j = 0;j < d - 1; j++) {
            del = del.next;
        }
        //删除节点
        prev.next = del.next;
        return head;
    }

    public int listLen(ListNode head) {
        int len = 1;
        ListNode cur = head;
        while(cur.next != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }
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

二、两两交换链表中的节点

2.1 题目描述

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

---

---

---

2.2 思路分析

按照题目来看，默认给定的链表节点值的个数是偶数（除去一个节点和空链表的情况），对这个链表的节点值进行两两交换，可以有如下分析：

• 当链表为空或是只有一个节点时，返回链表头结点
• 定义一个哨兵节点并将他的next指向链表头结点，定义一个辅助交换的节点tmp，它初始指向哨兵节点，当这个辅助节点的下一个不为空并且它的下一个的下一个不为空时进入循环，定义第一个节点指针指向tmp的next，定义第二个节点指针指向tmp.next.next，开始交换，就是将这两个节点的指向交换一下位置，循环遍历整个链表，最后返回哨兵位的下一个节点即头节点。

2.3 代码演示

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //定义哨兵节点
        ListNode prev = new ListNode(0);
        prev.next = head;
        //定义交换辅助节点
        ListNode tmp = prev;
        while(tmp.next != null && tmp.next.next != null) {
            //定义第一个节点指针
            ListNode start = tmp.next;
            //定义第二个节点指针
            ListNode end = tmp.next.next;
            //开始交换
            tmp.next = end;
            start.next = end.next;
            end.next = start;
            tmp = start;
        }
        return prev.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、随机链表的复制

3.1 题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

3.2 思路分析

开始看到这道题的时候我是很懵的状态，完全看不懂题目是什么意思，后来才慢慢理解，先来解释一下题目的要求：

• 给定一个特殊的链表，就是普通的链表多加了一个节点，这个多加的节点随机指向链表上的某个节点或指向空，多个随机节点可以指向同一个节点，按我的判断，虽说这个随机节点的指向是“随机”的，但其实并不用太关注它的指向，因为题目给的链表中的所有节点的指向都已经确定了，只要将这个链表复制一份形成一个新链表就可以了。

接下来对这道题进行解题思路分析：

• 因为是对链表进行拷贝，最终是会有两个不同的链表，可以考虑使用Map集合，在向集合中添加元素的时候，旧链表的节点作为键，同时这个键对应的值是新创建的节点，新创建的节点值就是旧链表的节点值，当遍历完链表，map集合中就收集了两个链表的信息；再次遍历链表，每次遍历根据map集合中的键（旧链表节点）找到值（新链表节点），再将当前节点的next指针（旧链表的第二个节点）作为键找出它在map集合中对应的值（新链表的第二个节点），将第一个值的next指向第二个值（就是将新链表形成链表结构），再根据当前节点的random（random节点指向是由旧链表提供好的）作为键拿到它在map集合中对应的值（就是新链表random所指向的节点），将它作为由map集合根据键找出来的新链表的节点的random的指向，最后返回head作为键找到的值（就是新链表的头节点）。

---

---

3.3 代码演示

public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node,Node> map = new HashMap<>();
        //遍历链表，向map集合中添加原链表节点作为键和新链表节点作为值
        //并为新链表节点赋值
        while(cur != null) {
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        //重新指向头节点
        cur = head;
        //遍历map集合，在遍历的过程中更新新链表
        while(cur != null) {
            //更新map集合中的值的next指针
            map.get(cur).next = map.get(cur.next);
            //更新map集合中的值的random指针
            map.get(cur).random = map.get(cur.random);
            cur = cur.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
21
22
23
24