跳转至

链表

2. 两数相加

难度：⭐️

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

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

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

示例1：

两数相加

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解法一 直接相加

用头结点占位，遍历相加并保存进位标识。注意加上最后一个进位的值。每一位计算的结果建议创建新节点，复用节点虽然会节省空间，但是会破坏原链表的结构。

时间复杂度：O(max(m, n))
空间复杂度：O(1)

两数相加 
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode head = new ListNode();
      ListNode p = head;
      int carry = 0;
      while (l1 != null || l2 != null || carry > 0) {
          ListNode next = new ListNode();
          if (l1 != null) {
              next.val += l1.val;
              l1 = l1.next;
          }
          if (l2 != null) {
              next.val += l2.val;
              l2 = l2.next;
          }
          if (carry > 0) {
              next.val += carry;
          }
          carry = next.val / 10;
          next.val %= 10;
          p.next = next;
          p = p.next;
      }
      return head.next;
  }

21. 合并两个有序链表

难度：⭐️

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法一 迭代

直接循环，将指针每次都指向较小的节点。

迭代 
public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    ListNode p1 = list1;
    ListNode p2 = list2;
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1 != null) {
        p.next = p1;
    } else if (p2 != null) {
        p.next = p2;
    }
    return dummy.next;
}

解法二 递归

比较头结点，较小的节点的next作为一个子链表，递归和另一个链表比，返回较小节点。其中一个节点为空时，返回另一个节点，递归中止。

递归放 
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

23.合并 K 个升序链表

难度：⭐️⭐️⭐️⭐️

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法一 顺序合并

两两合并，按顺序合并。注意不能排序，否则会超时

顺序合并 
  public ListNode mergeKLists(ListNode[] lists) {
      ListNode head = null;
      for (int i = 0; i < lists.length; i++) {
          head = mergeLists(head, lists[i]);
      }
      return head;
  }

  private ListNode mergeLists(ListNode list1, ListNode list2) {
      if (list1 == null) {
          return list2;
      }
      if (list2 == null) {
          return list1;
      }
      ListNode dummy = new ListNode(-1);
      ListNode p = dummy;
      ListNode p1 = list1;
      ListNode p2 = list2;
      while (p1 != null && p2 != null) {
          if (p1.val < p2.val) {
              p.next = p1;
              p1 = p1.next;
          } else {
              p.next = p2;
              p2 = p2.next;
          }
          p = p.next;
          if (p1 == null) {
              p.next = p2;
          }
          if (p2 == null) {
              p.next = p1;
          }
      }
      return dummy.next;
  }

解法二 分治

将数组分成2部分，头尾排序，递归调用。

分治 
  public ListNode mergeKLists(ListNode[] lists) {
      return merge(lists, 0, lists.length - 1);
  }

  private ListNode merge(ListNode[] lists, int start, int end) {
      if (start == end) {
          return lists[start];
      } else if (start > end) {
          return null;
      } else {
          int mid = (end + start) >> 1;
          return mergeLists(merge(lists, start, mid), merge(lists, mid + 1, end));
      }
  }

  private ListNode mergeLists(ListNode list1, ListNode list2) {
      if (list1 == null) {
          return list2;
      }
      if (list2 == null) {
          return list1;
      }
      ListNode dummy = new ListNode(-1);
      ListNode p = dummy;
      ListNode p1 = list1;
      ListNode p2 = list2;
      while (p1 != null && p2 != null) {
          if (p1.val < p2.val) {
              p.next = p1;
              p1 = p1.next;
          } else {
              p.next = p2;
              p2 = p2.next;
          }
          p = p.next;
          if (p1 == null) {
              p.next = p2;
          }
          if (p2 == null) {
              p.next = p1;
          }
      }
      return dummy.next;
  }

解法三 优先级队列

将所有链表的头结点加入优先级队列中，最前面的即为最小值，每次循环，将最小值排序并将最小值的next入队，直到队列为空。

优先级队列 
  public ListNode mergeKLists(ListNode[] lists) {
      PriorityQueue<ListNode> queue = new PriorityQueue<>((ListNode n1, ListNode n2) -> {
          return n1.val - n2.val;
      });
      for (ListNode node : lists) {
          if (node != null) {
              queue.offer(node);
          }
      }
      ListNode head = new ListNode(-1);
      ListNode p = head;
      while (!queue.isEmpty()) {
          ListNode min = queue.poll();
          p.next = min;
          if (min.next != null) {
              queue.offer(min.next);
          }
          p = p.next;
      }
      return head.next;
  }

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

难度：⭐️⭐️

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

解法一 直接交换

运用占位的前驱节点，同时记录前序节点和当前节点。

直接交换 
  public ListNode swapPairs(ListNode head) {
      ListNode dummy = new ListNode();
      dummy.next = head;
      ListNode pre = dummy;
      ListNode p = head;
      // 1 -> 2 -> 3
      while (p != null && p.next != null) {
          // 2
          ListNode next = p.next;
          // 1 -> 3
          p.next = next.next;
          // 2 -> 1 -> 3
          next.next = p;
          // * -> 2 -> 1 -> 3
          pre.next = next;
          pre = p;
          p = p.next;
      }
      return dummy.next;
  }

解法二 递归

递归结束的条件是只有一个节点，或者到链表的末尾。

直接交换 
  public ListNode swapPairs(ListNode head) {
      if (head == null || head.next == null) {
          return head
      }
      ListNode next = head.next
      head.next = swapPairs(next.next)
      next.next = head
      return next
  }

25.K个一组翻转链表

难度：⭐️⭐️⭐️⭐️

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

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

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

解法一 模拟

本题细节较多，核心思路是找到需要翻转的序列，对该序列的链表进行翻转。

模拟 
  public ListNode reverseKGroup(ListNode head, int k) {
      ListNode dummy = new ListNode(-1);
      ListNode pre = dummy;
      pre.next = head;
      ListNode tail = head;
      while (tail != null) {
          for (int i = 0; i < k - 1; i++) {
              if (tail.next != null) {
                  tail = tail.next;
              } else {
                  return dummy.next;
              }
          }
          ListNode next = tail.next;
          ListNode[] temp = reverse(head, tail);
          pre.next = temp[0];
          pre = temp[1];
          pre.next = next;
          head = next;
          tail = head;
      }
      return dummy.next;
  }

  private ListNode[] reverse(ListNode head, ListNode tail) {
      ListNode pre = tail.next;
      ListNode p = head;
      while(pre != tail) {
          ListNode next = p.next;
          p.next = pre;
          pre = p;
          p = next;
      }
      return new ListNode[]{tail, head};
  }

138.随机链表的复制

难度：⭐️⭐️⭐️

给你一个长度为 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 作为传入参数。

解法一 递归 + 哈希表

使用额外空间（哈希表，<旧节点，新节点>）保存已经复制过的链表，复制每个节点时，先从哈希表中查，能查到直接返回，查不到则新创建节点，递归复制next和random。需要额外注意的是，每次创建后应当立即将新节点放到哈希表中，然后再递归，否则会栈溢出。

时间复杂度：O(n)
空间复杂度：O(n)

递归+哈希表 
  private Map<Node, Node> cache = new HashMap<>();

  public Node copyRandomList(Node head) {
      if (head == null) {
          return null;
      }
      Node copy = cache.get(head);
      if (copy == null) {
          copy = new Node(head.val);
          cache.put(head, copy);
          copy.next = copyRandomList(head.next);
          copy.random = copyRandomList(head.random);
      }
      return copy;
  }

解法二 哈希表 + 非递归

两次遍历，第一次先把节点都复制一遍，存在哈希表中，第二次遍历把节点连接上。

时间复杂度：O(n)
空间复杂度：O(n)

哈希表 
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while (p != null) {
            map.put(p, new Node(p.val));
            p = p.next;
        }
        p = head;
        while (p != null) {
            Node q = map.get(p);
            if (p.next != null) {
                q.next = map.get(p.next);
            }
            if (p.random != null) {
                q.random = map.get(p.random);
            }
            p = p.next;
        }
        return map.get(head);
    }
}

解法三 迭代

第一次遍历，先把复制的节点接在原节点的后面，A -> B -> C 变成 A -> A' -> B -> B' -> C -> C'，此时原链表的节点random都指向原链表的节点，新节点的random都为空；
第二次遍历，根据原链表的random可以找到原节点，把新节点的random赋上值 第三次遍历，每次走两个节点，第二个节点是新链表的节点。

也可以把第三次遍历拆节点放到第二次遍历时，边遍历边拆。

141.环形链表I

难度：⭐

给你一个链表的头节点 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 或者链表中的一个 有效索引 。

解法一： 哈希表

把访问过的节点保存起来，指针一直往后走，当遇到存在一个结点被访问过时，就说明存在环。

时间复杂度：O(n)
空间复杂度：O(n)

快慢指针 
    public boolean hasCycle(ListNode head) {
        Set<ListNode> list = new HashSet<>();
        while (head != null) {
            if (list.contains(head)) {
                return true;
            }
            list.add(head);
            head = head.next;
        }
        return false;
    }

解法二： 快慢指针

快慢指针都从头结点开始，快指针每次只访问一个节点，慢指针每次访问两个个，两个节点相遇时，即说明有环。

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

快慢指针 
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

解法三：标记

由于题目中规定了链表的值 -105 <= Node.val <= 105，可以在遍历到每个节点之后，加一个固定的偏移，比如 200000，这样遍历过的节点 val 值都超过了 100000。

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

142.环形链表II

难度：⭐⭐

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

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

不允许修改 链表。

解法一： 哈希表

把访问过的节点保存起来，指针一直往后走，当遇到存在一个结点被访问过时，就说明存在环，该节点即为已经访问过的节点。

时间复杂度：O(n)
空间复杂度：O(n)

哈希表 
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

解法二： 快慢指针

快慢指针都从头结点开始，快指针每次只访问一个节点，慢指针每次访问 2 个，两个节点相遇时，即说明有环。这个算法叫Floyd判圈算法。

推导过程： 

head ──a──> 环入口 ──b──> 相遇点
                ↑            │
                └────c───────┘
设圈的长度为 L = b + c，相遇时：

  • 慢指针走 a + b
  • 快指针走 a + b + nL

快指针走的总步数是慢指针的 2 倍，于是有：
2(a + b) = a + b + nL ==> a + b = nL ==> a + b = n(b + c) ==> a = c + (n - 1)(b + c) 即 a = c + (n-1)L，也就是说，当一个指针从头结点出发，另一个从相遇点出发，以同样的速度前进，最终一定是在环入口相遇。

唯一需要注意的是，两个指标必须同时从头结点开始出发。

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

快慢指针 
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }

146.LRU缓存

难度：⭐️⭐️⭐️

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解法一 双向链表 + 哈希表

使用双向链表记录LRU中的节点的顺序，使用哈希表保持插入的值，移除节点时用双向列表可以保证时间复杂度为O(1).

双向链表 + 哈希表 ```java class LRUCache { class Node { int key; int value; Node prev; Node next; Node(int key, int value) { this.key = key; this.value = value; } } private int capacity; private int size; private Map cache; private Node head; private Node tail; public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; this.cache = new HashMap<>(capacity); this.head = new Node(-1, -1); this.tail = new Node(-1, -1); head.next = tail; tail.prev = head; } public int get(int key) { Node node = cache.get(key); if (node == null) { return -1; } else { moveToHead(node); return node.value; } } public void put(int key, int value) { Node node = cache.get(key); if (node == null) { node = new Node(key, value); cache.put(key, node); size++; addToHead(node); if (size > capacity) { Node last = removeLast(); cache.remove(last.key); } } else { node.value = value; moveToHead(node); } } private void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } private void addToHead(Node node) { Node next = head.next; node.next = next; next.prev = node; node.prev = head; head.next = node; } private Node removeLast() { Node node = tail.prev; removeNode(node); return node; } } ```

160.相交链表

难度：⭐️

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

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

相交链表

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

解法一 Hash集合

先一次遍历，将其中一个链表的值放在Set中存起来，再遍历另一个链表，结点在Set中存在，则说明相交。

Hash集合 
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode pa = new ListNode();
        pa.next = headA;
        while (pa.next != null) {
            set.add(pa.next);
            pa = pa.next;
        }
        ListNode pb = new ListNode();
        pb.next = headB;
        while (pb.next != null) {
            if (set.contains(pb.next)) {
                return pb.next;
            }
            pb = pb.next;
        }
        return null;
    }

解法二 双指针

用两个指针，初始分别指向头结点，遍历完之后，将尾节点接到另一条链表上，如果最终两个指针可以相遇，说明相交。

双指针 
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pa = headA;
    ListNode pb = headB;
    while (pa != pb) {
        pa = pa == null ? headB : pa.next;
        pb = pb == null ? headA : pb.next;
    }
    return pa;
}

234. 回文链表

难度：⭐️⭐️

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

解法一：复制到数组后双指针

先遍历一遍，把节点存到 list 中，然后用双指针分别指向头尾，向中间遍历。

时间复杂度：O(n)
空间复杂度：O(n)

集合 + 双指针 
public boolean isPalindrome(ListNode head) {
    List<ListNode> list = new ArrayList<>();
    ListNode p = head;
    while(p != null) {
        list.add(p);
        p = p.next;
    }
    int left = 0;
    int right = list.size() - 1;
    while(left < right) {
        if (list.get(left).val != list.get(right).val) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}