链表

Posted on Edited on In Word count in article: 4.2k Reading time ≈ 15 mins.
Linked List

#algorithm/linkedList # 206. 反转链表

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

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

三指针

/**
 * 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) {
        ListNode prev = null, cur = head, next;
        while(cur != null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

递归

/**
 * 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 || head.next == null)return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}
/**
 * 以链表1->2->3->4->5举例
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        /*
            直到当前节点的下一个节点为空时返回当前节点
            由于5没有下一个节点了，所以此处返回节点5
         */
        return head;
    }
    //递归传入下一个节点，目的是为了到达最后一个节点
    ListNode newHead = reverseList(head.next);
            /*
        第一轮出栈，head为5，head.next为空，返回5
        第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
                  把当前节点的子节点的子节点指向当前节点
                  此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
                  此时链表为1->2->3->4<-5
                  返回节点5
        第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
                  此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
                  此时链表为1->2->3<-4<-5
                  返回节点5
        第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
                  此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
                  此时链表为1->2<-3<-4<-5
                  返回节点5
        第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
                  此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
                  此时链表为1<-2<-3<-4<-5
                  返回节点5
        出栈完成，最终头节点5->4->3->2->1
     */
    head.next.next = head;
    head.next = null;
    return newHead;
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路： 根据题目意思 如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。

为此，我们必须消除两个链表的长度差

  • 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
  • 如果 pA 到了末尾，则 pA = headB 继续遍历
  • 如果 pB 到了末尾，则 pB = headA 继续遍历

比较长的链表指针指向较短链表head时，长度差就消除了 如此，只需要将最短链表遍历两次即可找到位置

source code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        if(a == null || b == null)return null;
        while(a != b){
            if(a == null) a = headB;
            else a = a.next;
            
            if(b == null) b = headA;
            else b = b.next;
        }

        return a;
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

思路： 快慢指针 fast 走两步 slow 走一步，如果是环最后肯定会相遇

source code 

class Solution(object):
    def hasCycle(self, head):
        if head == None:
            return False
        fast, slow = head, head

        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

            if slow == fast: 
                return True

        return False

142. 环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引 # 92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n 思路：

source code 

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        p0 = dummy
        for _ in range(left - 1):
            p0 = p0.next
        
        pre = None
        cur = p0.next
        for _ in range(right - left + 1):
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next

        p0.next.next = cur
        p0.next = pre
        
        return dummy.next

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

\(L0 → L1 → … → Ln - 1 → Ln\)

请将其重新排列后变为：

\(L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …\)

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

思路： 找到链表的midNode, 然后反转mid作为head2 依次连接head1和head2 source code 

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        mid = self.middleNode(head)
        head2 = self.reverse(mid)
        while head2.next:
            next = head.next
            next2 = head2.next
            head.next = head2
            head2.next = next
            head = next
            head2 = next2
        

    def reverse(self, head):
        prev, cur = None, head
        while cur:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev
    
    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000 思路：

步骤分解:

  1. 链表分区为已翻转部分+待翻转部分+未翻转部分

  2. 每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定

  3. 需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来

  4. 初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾

  5. 经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next

  6. 翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环

  7. 特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可

  8. 时间复杂度为 \(O(n * K)\) 最好的情况为 \(O(n)\) 最差的情况未 \(O(n^2)\)

  9. 空间复杂度为 \(O(1)\) 除了几个必须的节点指针外，我们并没有占用其他空间 

    class Solution:
        def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
            dummy = ListNode(0)
            dummy.next = head
            
            pre = dummy
            end = dummy

            while end.next:
                for i in range(k):
                    end = end.next
                    if not end: break
                if not end: break

                start = pre.next
                next = end.next
                end.next = None

                pre.next = self.reverse(start)
                start.next = next
                
                end = start
                pre = end
                
            return dummy.next

        def reverse(self, head):
            prev, cur = None, head
            while cur:
                next = cur.next
                cur.next = prev
                prev = cur
                cur = next
            return prev```

    # [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)

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

    **示例 1：**

    ![](https://images-a2q.pages.dev/file/5421eaf11160125493b92.png)

    输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 

    **示例 2：**

    输入：head = [1], n = 1 输出：[] 

    **示例 3：**

    输入：head = [1,2], n = 1 输出：[1] 

    **提示：**

    - 链表中结点的数目为 `sz`
    - `1 <= sz <= 30`
    - `0 <= Node.val <= 100`
    - `1 <= n <= sz`

    **思路：**
    - 设置虚拟节点 `dummy` 指向 `head`
    - 设定双指针 `slow` 和 `fast` ，初始都指向虚拟节点 `dummy`
    - 移动 `fast`，直到 `slow` 与 `fast` 之间相隔的元素个数为 `n`
    - 同时移动 `slow` 与 `fast`，直到 `fast` 指向的为 `None`
    - 将 `slow` 的下一个节点指向下下个节点

    **source code**

    ```python
    class Solution:
        def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
            dummy = ListNode(0)
            dummy.next = head

            slow = dummy
            fast = dummy
            for i in range(n - 1):
                fast = fast.next
            
            while fast.next:
                slow = slow.next
                fast = fast.next

            slow.next = slow.next.next

            return dummy.next

思路：

弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。

source code

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        stack = list()
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        
        for i in range(n):
            stack.pop()

        prev = stack[-1]
        prev.next = prev.next.next
        return dummy.next

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

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

思路： 把重复节点删除即可

source code 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head

        dummy = ListNode(0,head)

        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                x = cur.next.val
                while cur.next and cur.next.val == x:
	                # 代表删除节点
                    cur.next = cur.next.next
            else:
                cur = cur.next
        
        return dummy.next

1261. 在受污染的二叉树中查找元素

给出一个满足下述规则的二叉树：

  1. root.val == 0
  2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
  3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

  • FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
  • bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

提示：

  • TreeNode.val == -1
  • 二叉树的高度不超过 20
  • 节点的总数在 [1, 10^4] 之间
  • 调用 find() 的总次数在 [1, 10^4] 之间
  • 0 <= target <= 10^6

思路： 方法一：哈希表 从 \(\textit{root}\) 出发 DFS 这棵树，除了传入当前节点 \(\textit{node}\)，还传入需要还原的值 \(\textit{val}\)。

递归左儿子：传入 \(\textit{val}\cdot 2 + 1\)。

递归右儿子：传入 \(\textit{val}\cdot 2 + 2\)。

递归的同时，把还原后的节点值加到一个哈希表中。这样对于 \(\texttt{find}\)，只需要看 \(\textit{target}\)是否在哈希表中即可。

source code 

class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        s = set()
        def dfs(node: Optional[TreeNode], val: int) -> None:
            if node is None:
                return
            s.add(val)
            dfs(node.left, val * 2 + 1)
            dfs(node.right, val * 2 + 2)
        dfs(root, 0)
        self.s = s

    def find(self, target: int) -> bool:
        return target in self.s

148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

ww 

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

思路:

归并排序（递归法）

source code 

class Solution:
    def sortList(self, head: Optional[ListNode]) -%3E Optional[ListNode]:
        if not head or not head.next: return head

        slow, fast = head, head.next
        
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next

        mid, slow.next = slow.next, None

        left, right = self.sortList(head), self.sortList(mid)

        h = res = ListNode(0)
        while left and right:
            if left.val %3C right.val:
                h.next, left = left, left.next
            else:
                h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next