算法-链表技巧总结

Author：空夜
发布时间：February 8, 2021
3846 views
One comment
15291 words
Categories：算法

# 链表

分类：

- 单链表
- 双链表

特点：

- 链表对按索引（下标）查找不友好，时间复杂度O(n)
- 对插入友好，O(1)

遍历：

- 迭代：next 指针的存在使得链表可以使用 while 循环进行迭代
- 递归：链表的结构决定了它可以递归，比如打印当前链表：

```java
public static void print(ListNode head) {
    if (head == null) {
        return;
    }
    
    System.out.println(head.val);
    print(head.next); // 递归
}
```

技巧：

- 双指针技巧：一快一慢、一先一后
- 哨兵：设置一个伪节点作为 head 的 prev，或者作为 tail 的 next，以便在循环中一致地处理每一个节点

本节目前涵盖了 LeetCode  141，142，160，19，206，203，328，234，21，2，430，138，61 题，部分题目的解法还要参考 LeetCode 上的一些题解进行进一步的理解、优化；

---

## 环形链表-双指针技巧

### 1. 判定链表中是否存在环-141

双指针技巧

问题：如何判定链表中有环？

- 用哈希表，已经存在相同的 key，就表示出现了环
- 双指针技巧：如果出现了环，那么快的指针最终一定会与慢指针相遇；

双指针技巧实现：

- 慢指针每次走1步，快指针每次走2步，可知，假设存在环，那么在慢指针还没开始走第二圈的时候，快指针已经追上了慢指针（极端情况是链表首尾相连，此时，刚好在慢指针走完第一圈时，快指针走完了第二圈，相遇点=环的入口）
- 每次快指针多走一步，当快慢指针相遇时，快指针已经绕环走了 S 圈（S为环的长度）

```java
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean res = false;

ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (slow == null || fast == null) {
                break;
            }

fast = fast.next; // fast 多走一步
            if (slow == fast) {
                res = true;
                break;
            }
        }

return res;
    }
}
```

---

### 2. 找到环的入口-142

思路：

1. 用哈希表存，找到第一个重复的节点
1. 用快慢指针法，根据规则推算，从 head 到环入口的长度=相遇点到入环点的距离 + (n-1) 圈的环长

> 推导公式，可知：从 head 到入环点的距离，等于 fast和slow 第一次相遇点开始到入环点的距离 + (n-1) * 环长
> 也就是说：当 fast 和 slow 相遇时，ptr 从 head 出发，slow 从相遇点出发，第一次相遇必然在入环点

```java
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

ListNode slow = head;
        ListNode fast = head;
        while (slow != null) {

if (fast.next == null || fast.next.next == null) {
                return null;
            }

slow = slow.next;
            fast = fast.next.next;

if (slow == fast) {
                ListNode ptr = head;
                while (slow != ptr) {
                    slow = slow.next;
                    ptr = ptr.next;
                }

return ptr;
            }
        }

return null;
    }
```

---

### 3. 如何判断两个单向链表是否相交，如果相交，那么找出相交点-160

解法，如果相交，那么我们可以让链表 A 的尾部连接到链表 B 的 head，这样就会形成一个环。此时，判定是否相交就是找这个新链表的入环点。

```java
 /**
     * 获取两个链表相交的点
     * 假设链表中不存在环
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

// 找到第一个链表的尾部
        ListNode cur = headA;
        while (cur.next != null) {
            cur = cur.next;
        }

// 将第一个链表的 tail 连接到第二个链表的 head，这样就形成了环
        // 根据环形链表中的结论：从 head 出发到入环点的距离 = (n-1) * 环圈 + 相遇点-入环点
        cur.next = headB;
        // 用快慢指针法找到相遇点
        ListNode slow = headA;
        ListNode fast = headA;
        while (slow != null && fast != null) {
            if (slow.next == null || fast.next == null || fast.next.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;

if (slow == fast) {
                ListNode ptr = headA;
                // 从相遇点出发
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }

cur.next = null;
                return ptr;
            }
        }

cur.next = null;

return null;
    }
```

---

### 4. 删除倒数第 n 个节点-19

在 O(n) 时间复杂度内删除倒数第 n 个节点

> 用快慢指针法，快指针先走 n 步，然后快慢指针一起走，当快指针到达链表尾部时，删掉慢指针所在节点；

```java
 /**
     * 两个指针，fast 先走 n 步，然后 slow 出发，当 fast.next == null 时，删掉 slow
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

// 初始化 fast 和 head 两个指针，让 fast 先走 n 步
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < n - 1; i++) {
            if (fast.next == null) {
                return null;
            }

fast = fast.next;
        }

// 上面走了 n - 1 步，再走一步
        if (fast.next == null) {
            // 这一步表示达到末尾了，也就是要删除第一个元素
            return head.next;
        }

fast = fast.next;

// fast 和 slow 一起走，直到 fast 达到链表尾部，此时，slow 位置就是要删除的节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return head;
    }
```

---

## 经典问题

### 1. 反转链表-206

- 迭代：一次遍历，从 head 开始，顺序迭代，每次都将 head 的下一个节点放到链表头部，时间复杂度 O(n)，空间复杂度 O(1)
- 递归：每次递归，将第一个节点放到最后；递归需要堆栈，空间复杂度变为 O(n)；（所以对于这一题，还是迭代的方式很简洁）

#### 迭代

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

// 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

return lastHead;
    }
```

#### 递归

```java
    public static ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }

ListNode last = reverse(head.next);
        head.next.next = head; // 把 head 放到 last 的尾部，这样 head 就完成了反转
        head.next = null;
        return last;
    }
```

---

扩展：

参考：[递归反转链表的一部分](https://labuladong.gitee.io/algo/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E9%80%92%E5%BD%92%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8%E7%9A%84%E4%B8%80%E9%83%A8%E5%88%86.html)

#### 1.1 反转链表前 N 个节点

- 迭代
- 递归

递归实现：

```java
public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 结束递归
            successor = head.next;
            return head;
        }

// 反转后面的元素
        ListNode last = reverseN(head.next, n-1);
        // 将 head 放到第 N + 1 节点前面, 原来的 head.next 已经变成了 last 的tail
        head.next.next = head;
        head.next = successor;
        return last;
}
```

#### 1.2 反转链表某一部分

```java
/**
     * 反转链表 m - n 中的节点，m >= 1, n <= 链表长度
     * @return
     */
    public static ListNode reverseMN(ListNode head, int m, int n) {
        if (m == 1) {
            // 此时相当于反转链表的前 n 个节点
            return reverseN(head, n);
        }

// 如果 m > 1，那么我们递归去反转 head.next
        head.next = reverseMN(head.next, m - 1, n - 1);
        return head;
    }	
```

#### 1.3 k 个一组反转链表-25

LeetCode 25 题，难度：高
[https://leetcode-cn.com/problems/reverse-nodes-in-k-group/](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)

思路：

- 反转前 k 个结点，然后递归反转 x * k+1 结点开始的 k 个结点
- 递归结束条件：直到链表剩余结点数小于 k
- 需要准备的方法：反转前 k 个结点

---

### 2. 移除链表元素-203

移除 val 等于指定值的节点，分为两种情况：

- 非 head 位置的元素，如果需要删除，只要 prev.next = cur.next 即可
- head 位置的元素，如果需要删除，那么就要将 head = head.next 才行

解决办法：

1. 首先将位于最前面的需要删除的元素删除，确保之后要删除的节点不在 head 位置，然后遍历一遍即可
1. 设置一个哨兵作为伪节点，让 sentinel.next = head，从 sentinel 位置开始遍历即可

第二种的代码：

```java
    public static ListNode removeElements(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1); // 哨兵
        sentinel.next = head;

ListNode far = sentinel;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                far.next = cur.next;
            } else {
                far = cur;
            }
            cur = cur.next;
        }

return sentinel.next;
    }
```

---

### 3. 奇偶链表-328

- [ ] 待优化

```java
/**
     * 奇偶转换
     * 奇数位置的节点顺序在前，偶数位置的节点顺序在后
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

ListNode evenHead = null;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next; // 偶数
            if (evenHead == null) {
                evenHead = cur;
            } else {
                evenHead.next = cur;
            }

if (cur == null) {
                break;
            }
            cur = cur.next; // 奇数
        }

return head;
    }
```

---

### 4. 回文链表-234

- 方法 1： List 存储所有节点，两两对比， O(2*n) 时间复杂度，O(n) 空间复杂度
- 方法 2：直接反转整个链表，然后分别读两个链表；时间复杂度 O(n)，空间复杂度 O(n)
- 方法 3：在方法2 基础上进行的优化 —— 用快慢指针找到中间节点，然后反转链表后半部分，然后让指针分别从 head 和 mid 出发来进行比较

方法 2，O(n) 时间复杂度的解法：

- 用快慢指针法找到中间节点，时间 n/2
- 反转链表后半部分, n/2
- 用双指针分别顺序遍历前半部分和后半部分，挨个比较，最坏情况是 O(n/2)
- 再次反转链表后半部分，以恢复链表 n/2

时间复杂度 O(n)，空间复杂度 O(1)

```java
class Solution {
     /**
     * 判定链表是否为回文字符串
     *
     * 1-2 false
     * 1-2-2-1 true
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        
        if (head == null || head.next == null) {
            return true;
        }

ListNode mid = findMid(head);

// 反转链表后半部分
        ListNode fast = reverseList(mid.next);

ListNode slow = head;
        while (slow != mid.next && fast != null) {
            // 注意判定条件，在节点为偶数的情况下，slow 最后等于 mid
            // 在奇数情况下， slow.next 最后等于 mid -> 这种情况，要额外判断一下 fast 是否已经达到末尾了
            if (slow.val != fast.val) {
                reverseList(mid.next);
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }

reverseList(mid.next);
        return true;
    }

/**
     * 找到链表的中间节点
     * 1-2-3-4 => 2
     * 1-2-3 => 2
     * @param head
     * @return
     */
     static ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }
        return slow;
    }

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

// 1-2-3-4-5 -> 5-4-3-2-1
        // 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

return lastHead;
    }
}
```

---

## 扩展问题

### 1. 合并两个有序链表-21

```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 思路：都插入到新链表中，这样只需要遍历 O(n)

ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        ListNode a = l1;
        ListNode b = l2;
        while (true) {

if (a == null && b == null) {
                break;
            } else {
                if (a == null) {
                    cur.next = b;
                    b = b.next;
                } else if (b == null) {
                    cur.next = a;
                    a = a.next;
                } else {
                    if (a.val <= b.val) {
                        cur.next = a;
                        a = a.next;
                    } else {
                        cur.next = b;
                        b = b.next;
                    }
                }
                cur = cur.next;
            }
        }

return sentinel.next;
    }
```

---

### 2. 两数相加-2

> 题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

> 请你将两个数相加，并以相同形式返回一个表示和的链表。

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

```java
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(-1);
        ListNode aCur = l1;
        ListNode bCur = l2;
        ListNode rCur = sentinel;
        int carryNum = 0;
        int thisSum = 0;
        while (true) {
            if (aCur == null && bCur == null) {
                if (carryNum > 0) {
                    rCur.next = new ListNode(carryNum);
                }
                break;
            }

thisSum = carryNum;
            if (aCur == null) {
                thisSum += bCur.val;
                bCur = bCur.next;
            } else if (bCur == null) {
                thisSum += aCur.val;
                aCur = aCur.next;
            } else {
                thisSum += (aCur.val + bCur.val);
                aCur = aCur.next;
                bCur = bCur.next;
            }

carryNum = 0;
            if (thisSum >= 10) {
                thisSum = thisSum - 10;
                carryNum = 1;
            }
            rCur.next = new ListNode(thisSum);
            rCur = rCur.next;
        }

return sentinel.next;
    }
```

---

### 3. 扁平化多级双向链表-430

第一直觉：递归
为什么选择递归呢，因为每一个节点都可能有 child，而每一个 child 也都可能有自己的 child，子子孙孙无穷尽也。显然这里用递归是非常合适的。

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

Node next = null;
        if (head.child == null) {
            if (head.next != null) {
                next = flatten(head.next);
            }
        } else {
            Node oldNext = head.next;
            next = flatten(head.child);

if (oldNext != null) {
                Node newTail = next;
                while (newTail.next != null) {
                    newTail = newTail.next;
                }

newTail.next = oldNext;
                oldNext.prev = newTail;
            }
        }

head.child = null;
        head.next = next;
        if (next != null) {
            next.prev = head;
        }

return head;
    }
}
```

---

### 4. 复制带随机指针的链表-138

题目描述：链表中每个节点都有一个 random 指针，指向任意的其他节点或空节点。要求实现一个函数，实现链表的深拷贝。

思路：

- 用一个 map 存储原来节点和对应的拷贝节点，第一次遍历链表拷贝 val，第二次遍历链表拷贝 next 和 random

```java
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> copyMap = new HashMap<>();

// copy val
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copyMap.put(cur, copy);
            cur = cur.next;
        }

// copy next and random
        cur = head;
        while (cur != null) {
            Node copy = copyMap.get(cur);
            copy.next = copyMap.get(cur.next);
            copy.random = copyMap.get(cur.random);

cur = cur.next;
        }

return copyMap.getOrDefault(head, null);
    }
}
```

---

### 5. 旋转链表-61

解法：形成环，然后找到新的 head 并断开环

```java
public ListNode rotateRight(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return head;
        }
        int size = 0;
        ListNode tail = null;
        ListNode cur = head;
        while (cur != null) {
            size++;
            if (cur.next == null) {
                tail = cur;
            }
            cur = cur.next;
        }

// 变成环
        tail.next = head;

// 在合适的位置断开环
        int i = 0;
        k = k % size; // 取余数
        while (i < size - k) {
            tail = tail.next;
            i++;
        }

ListNode newHead = tail.next;
        tail.next = null;
        return newHead;
    }
```

Last modification：February 23, 2021

请作者喝杯肥宅快乐水吧！

One comment

ClearScenery
February 9th, 2021 at 12:03 am

吊人OωO

Reply

算法-链表技巧总结

空夜 • 2021 年 02 月 08 日

# 链表

分类：

- 单链表
- 双链表

特点：

- 链表对按索引（下标）查找不友好，时间复杂度O(n)
- 对插入友好，O(1)

遍历：

- 迭代：next 指针的存在使得链表可以使用 while 循环进行迭代
- 递归：链表的结构决定了它可以递归，比如打印当前链表：

```java
public static void print(ListNode head) {
    if (head == null) {
        return;
    }
    
    System.out.println(head.val);
    print(head.next); // 递归
}
```

技巧：

- 双指针技巧：一快一慢、一先一后
- 哨兵：设置一个伪节点作为 head 的 prev，或者作为 tail 的 next，以便在循环中一致地处理每一个节点

---

## 环形链表-双指针技巧

### 1. 判定链表中是否存在环-141

双指针技巧

问题：如何判定链表中有环？

- 用哈希表，已经存在相同的 key，就表示出现了环
- 双指针技巧：如果出现了环，那么快的指针最终一定会与慢指针相遇；

双指针技巧实现：

```java
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean res = false;

fast = fast.next; // fast 多走一步
            if (slow == fast) {
                res = true;
                break;
            }
        }

return res;
    }
}
```

---

### 2. 找到环的入口-142

思路：

1. 用哈希表存，找到第一个重复的节点
1. 用快慢指针法，根据规则推算，从 head 到环入口的长度=相遇点到入环点的距离 + (n-1) 圈的环长

```java
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

ListNode slow = head;
        ListNode fast = head;
        while (slow != null) {

if (fast.next == null || fast.next.next == null) {
                return null;
            }

slow = slow.next;
            fast = fast.next.next;

if (slow == fast) {
                ListNode ptr = head;
                while (slow != ptr) {
                    slow = slow.next;
                    ptr = ptr.next;
                }

return ptr;
            }
        }

return null;
    }
```

---

### 3. 如何判断两个单向链表是否相交，如果相交，那么找出相交点-160

解法，如果相交，那么我们可以让链表 A 的尾部连接到链表 B 的 head，这样就会形成一个环。此时，判定是否相交就是找这个新链表的入环点。

// 找到第一个链表的尾部
        ListNode cur = headA;
        while (cur.next != null) {
            cur = cur.next;
        }

cur.next = null;
                return ptr;
            }
        }

cur.next = null;

return null;
    }
```

---

### 4. 删除倒数第 n 个节点-19

在 O(n) 时间复杂度内删除倒数第 n 个节点

> 用快慢指针法，快指针先走 n 步，然后快慢指针一起走，当快指针到达链表尾部时，删掉慢指针所在节点；

fast = fast.next;
        }

// 上面走了 n - 1 步，再走一步
        if (fast.next == null) {
            // 这一步表示达到末尾了，也就是要删除第一个元素
            return head.next;
        }

fast = fast.next;

if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return head;
    }
```

---

## 经典问题

### 1. 反转链表-206

#### 迭代

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

return lastHead;
    }
```

#### 递归

```java
    public static ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }

ListNode last = reverse(head.next);
        head.next.next = head; // 把 head 放到 last 的尾部，这样 head 就完成了反转
        head.next = null;
        return last;
    }
```

---

扩展：

#### 1.1 反转链表前 N 个节点

- 迭代
- 递归

递归实现：

```java
public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 结束递归
            successor = head.next;
            return head;
        }

#### 1.2 反转链表某一部分

// 如果 m > 1，那么我们递归去反转 head.next
        head.next = reverseMN(head.next, m - 1, n - 1);
        return head;
    }	
```

#### 1.3 k 个一组反转链表-25

LeetCode 25 题，难度：高
[https://leetcode-cn.com/problems/reverse-nodes-in-k-group/](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)

思路：

- 反转前 k 个结点，然后递归反转 x * k+1 结点开始的 k 个结点
- 递归结束条件：直到链表剩余结点数小于 k
- 需要准备的方法：反转前 k 个结点

---

### 2. 移除链表元素-203

移除 val 等于指定值的节点，分为两种情况：

- 非 head 位置的元素，如果需要删除，只要 prev.next = cur.next 即可
- head 位置的元素，如果需要删除，那么就要将 head = head.next 才行

解决办法：

第二种的代码：

```java
    public static ListNode removeElements(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1); // 哨兵
        sentinel.next = head;

return sentinel.next;
    }
```

---

### 3. 奇偶链表-328

- [ ] 待优化

if (cur == null) {
                break;
            }
            cur = cur.next; // 奇数
        }

return head;
    }
```

---

### 4. 回文链表-234

方法 2，O(n) 时间复杂度的解法：

时间复杂度 O(n)，空间复杂度 O(1)

ListNode mid = findMid(head);

// 反转链表后半部分
        ListNode fast = reverseList(mid.next);

reverseList(mid.next);
        return true;
    }

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

return lastHead;
    }
}
```

---

## 扩展问题

### 1. 合并两个有序链表-21

```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 思路：都插入到新链表中，这样只需要遍历 O(n)

ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        ListNode a = l1;
        ListNode b = l2;
        while (true) {

return sentinel.next;
    }
```

---

### 2. 两数相加-2

> 题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

> 请你将两个数相加，并以相同形式返回一个表示和的链表。

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

return sentinel.next;
    }
```

---

### 3. 扁平化多级双向链表-430

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

if (oldNext != null) {
                Node newTail = next;
                while (newTail.next != null) {
                    newTail = newTail.next;
                }

newTail.next = oldNext;
                oldNext.prev = newTail;
            }
        }

head.child = null;
        head.next = next;
        if (next != null) {
            next.prev = head;
        }

return head;
    }
}
```

---

### 4. 复制带随机指针的链表-138

题目描述：链表中每个节点都有一个 random 指针，指向任意的其他节点或空节点。要求实现一个函数，实现链表的深拷贝。

思路：

- 用一个 map 存储原来节点和对应的拷贝节点，第一次遍历链表拷贝 val，第二次遍历链表拷贝 next 和 random

```java
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> copyMap = new HashMap<>();

// copy val
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copyMap.put(cur, copy);
            cur = cur.next;
        }

cur = cur.next;
        }

return copyMap.getOrDefault(head, null);
    }
}
```

---

### 5. 旋转链表-61

解法：形成环，然后找到新的 head 并断开环

// 变成环
        tail.next = head;

// 在合适的位置断开环
        int i = 0;
        k = k % size; // 取余数
        while (i < size - k) {
            tail = tail.next;
            i++;
        }

ListNode newHead = tail.next;
        tail.next = null;
        return newHead;
    }
```

算法-链表技巧总结

One comment

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

idea 激活码2020

Typecho搭建个人博客教程

SpringCloud服务健康监控

Mybatis居然可以连接 ClickHouse?

SpringCloud Nacos 配置中心

hexo 博客搭建

idea 激活码2020

SpringBoot中如何一次批量扫描Redis的键值对？

SpringCloud Nacos 配置中心

SpringSecurity+OAuth2实现单点登录SSO

算法-链表技巧总结

One comment

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

算法-链表技巧总结

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款