XCPC Wiki

Appearance

链表 ​

单链表由节点和指向后继的指针组成。定位一个节点通常需要顺序遍历，时间为 O(n)O(n)；已知前驱节点时，插入或删除其后继只需 O(1)O(1) 次指针操作。数组的随机访问、链表的局部修改和有序集合的查找具有不同语义，不能互相直接替代。

单链表模板 ​

以下模板使用 new 创建节点，由删除操作释放。insert 要求 p 非空；erase_next 要求存在待删除的后继。

cpp
struct Node {
  int val;
  Node* next;
};

void insert(Node* p, int val) {
  Node* node = new Node{val, p->next};
  p->next = node;
}

void erase_next(Node* pre) {
  Node* removed = pre->next;
  pre->next = removed->next;
  delete removed;
}

// 仅用于 p 非空且不是尾节点，并允许覆盖其值的场景。
void erase(Node* p) {
  Node* removed = p->next;
  p->val = removed->val;
  p->next = removed->next;
  delete removed;
}

erase(p) 通过复制后继值绕过寻找前驱，但真正销毁的是后继节点，不能用于尾节点，也不保持节点身份。若其他对象持有这些节点的指针，必须考虑引用是否失效。

以下题解使用 LeetCode 提供的 ListNode 类型，其成员为 val 和 next，并提供对应构造函数。各题函数独立使用；调用 reverseList 的题解复用反转链表一节的迭代实现。除环形链表两题外，默认输入无环；合并有序链表还假设两个输入不共享节点。

LeetCode 热门题目 ​

160. 相交链表 ​

题目链接

给定两个单链表的头节点指针 headA 和 headB，请找出并返回它们相交的起始节点指针。如果没有相交节点，返回 nullptr。

要求使用 O(1)O(1) 空间和 O(n+m)O(n + m) 时间复杂度。

直接法

首先分别遍历两个链表，统计它们的长度。然后让两个指针分别从头节点出发，长的那个链表先多走几步，使得两个指针后续等长后一起前进，每次比较当前节点是否相同。

这种方法思路较为直观，并且能满足题目要求的复杂度。

cpp
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  int len_a = 0, len_b = 0;
  ListNode *pa = headA, *pb = headB;
  while (pa)
    pa = pa->next, len_a++;
  while (pb)
    pb = pb->next, len_b++;
  pa = headA, pb = headB;
  while (len_a > len_b)
    pa = pa->next, len_a--;
  while (len_b > len_a)
    pb = pb->next, len_b--;
  while (pa != pb) {
    pa = pa->next;
    pb = pb->next;
  }
  return pa;
}
双指针法

可以注意到：指针先走链表一再走链表二，与先走链表二再走链表一，两者实际等长。因此可以让两个指针同时走，当一个指针走到末尾时跳到另一个链表头，最终两者要么在交点相遇，要么都到达 nullptr。

cpp
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  ListNode *pa = headA, *pb = headB;
  while (pa != pb) {
    pa = pa ? pa->next : headB;
    pb = pb ? pb->next : headA;
  }
  return pa;
}

哈希法：可以用 std::unordered_map 存储链表中的节点地址，然后遍历另一个链表查找。这种方法使用 O(n)O(n) 额外空间，不满足本题的常数辅助空间要求。

206. 反转链表 ​

题目链接

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

迭代法（插头法）

维护一个新的链表头，遍历原链表时，将当前节点插入到新链表头部。

cpp
ListNode *reverseList(ListNode *head) {
  ListNode *head2 = nullptr, *p = head;
  while (p) {
    ListNode *next = p->next;
    p->next = head2;
    head2 = p;
    p = next;
  }
  return head2;
}
递归法

如果存在后继节点，可以先递归反转后续部分，然后将当前节点插入到反转后链表的尾部即可。

cpp
ListNode *reverseList(ListNode *head) {
  if (head && head->next) {
    ListNode *head2 = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return head2;
  } else {
    return head;
  }
}

234. 回文链表 ​

题目链接

给定单链表的头节点 head，判断该链表是否为回文链表。

反转后半段

用快慢指针找到前半段末尾，反转后半段并逐一比较，最后把后半段反转回来。比较失败时也要先恢复链表再返回。该方法用 O(n)O(n) 时间和 O(1)O(1) 辅助空间。

cpp
bool isPalindrome(ListNode* head) {
  if (!head || !head->next) return true;
  ListNode *slow = head, *fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  ListNode* second = reverseList(slow->next);
  bool equal = true;
  for (ListNode *a = head, *b = second; b; a = a->next, b = b->next) {
    if (a->val != b->val) equal = false;
  }
  slow->next = reverseList(second);
  return equal;
}

141. 环形链表 ​

题目链接

给定链表的头节点 head，判断链表是否存在环。

Floyd 判环法

使用快慢指针（Floyd 判环算法），如果快慢指针最终相遇，则说明有环，否则无环。

cpp
bool hasCycle(ListNode *head) {
  ListNode *p1 = head, *p2 = head;
  while (p1 && p2 && p2->next) {
    p1 = p1->next;
    p2 = p2->next->next;
    if (p1 == p2)
      return true;
  }
  return false;
}

142. 环形链表 II ​

题目链接

给定链表头节点 head，返回链表开始进入环的第一个节点。如果没有环，返回 nullptr。

Floyd 判环法

假设快慢指针相遇时，慢指针走了 kk 步，快指针走了 2k2k 步。那么从链表头再设置一个新指针，每次一步，与原慢指针同步前进，两者会在入环节点相遇。

也可以理解为：相遇点到环入口的距离等于头节点到环入口的距离（模环长）。

cpp
ListNode *detectCycle(ListNode *head) {
  ListNode *p1 = head, *p2 = head;
  while (p1 && p2 && p2->next) {
    p1 = p1->next;
    p2 = p2->next->next;
    if (p1 == p2) {
      p2 = head;
      while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
      }
      return p1;
    }
  }
  return nullptr;
}

21. 合并两个有序链表 ​

题目链接

将两个升序链表合并为一个新的升序链表并返回，新链表通过拼接两个链表中的所有节点构成。

迭代法

维护指针逐步合并两个链表，每次选择较小的节点插入结果链表。

cpp
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
  ListNode tmp{-1000, nullptr};
  ListNode *p1 = list1, *p2 = list2, *p = &tmp;
  while (p1 && p2) {
    if (p1->val <= p2->val)
      p->next = p1, p1 = p1->next;
    else
      p->next = p2, p2 = p2->next;
    p = p->next;
  }
  p->next = p1 ? p1 : p2;
  return tmp.next;
}

递归法：递归合并两个链表的方法也很常见，推荐掌握。

2. 两数相加 ​

题目链接

给定两个非空链表，分别表示两个非负整数，数字按逆序存储，每个节点只存储一位数字。

链表高精度加法

本题实际上是链表实现的大数加法，依次处理进位即可。

cpp
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  ListNode tmp{0, nullptr};
  ListNode *p1 = l1, *p2 = l2, *p = &tmp;
  int carry = 0;
  while (p1 || p2 || carry) {
    int v = 0;
    if (p1)
      v += p1->val, p1 = p1->next;
    if (p2)
      v += p2->val, p2 = p2->next;
    v += carry;
    p->next = new ListNode(v % 10);
    p = p->next;
    carry = v / 10;
  }
  return tmp.next;
}

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

题目链接

给定一个链表，删除链表的倒数第 nn 个节点，并返回链表头节点。

双指针法

使用哑节点处理删除头节点的情况。快指针从哑节点先走 nn 步，然后两个指针同步前进，直到快指针到尾节点；慢指针此时是待删除节点的前驱。输入保证 1≤n≤1\le n\le 链表长度。

cpp
ListNode* removeNthFromEnd(ListNode* head, int n) {
  ListNode dummy{0, head};
  ListNode *fast = &dummy, *slow = &dummy;
  for (int i = 0; i < n; ++i) fast = fast->next;
  while (fast->next) {
    fast = fast->next;
    slow = slow->next;
  }
  ListNode* removed = slow->next;
  slow->next = removed->next;
  delete removed;
  return dummy.next;
}

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

题目链接

给定一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。要求不修改节点内部的值。

迭代法

关键在于每次交换时，正确维护前驱指针的位置。

cpp
ListNode* swapPairs(ListNode* head) {
  ListNode tmp{0, head};
  ListNode *pre = &tmp, *p = pre->next;
  while (p && p->next) {
    pre->next = p->next;
    p->next = p->next->next;
    pre->next->next = p;
    pre = p, p = p->next;
  }
  return tmp.next;
}

25. K 个一组翻转链表 ​

题目链接

给定链表的头节点 head，每 kk 个节点为一组进行翻转，返回修改后的链表。如果最后剩余节点不足 kk 个，则保持原顺序。

分组反转

p 始终指向待处理组的前驱。先向后检查是否有完整的 kk 个节点；不足则结束。保存下一组起点后断开当前组，调用迭代反转，再接回下一组。原组头变成组尾，也是下一轮的前驱。要求 k≥1k\ge1，总时间 O(n)O(n)、辅助空间 O(1)O(1)。

cpp
ListNode* reverseKGroup(ListNode* head, int k) {
  ListNode tmp{0, head};
  ListNode *p = &tmp;
  while (p) {
    ListNode *tail = p;
    for (int i = 0; i < k && tail; ++i)
      tail = tail->next;
    if (!tail)
      break;
    ListNode *front = p->next, *next = tail->next;
    tail->next = nullptr;
    p->next = reverseList(front);
    p = front;
    p->next = next;
  }
  return tmp.next;
}

138. 随机链表的复制 ​

题目链接

给定一个长度为 nn 的链表，每个节点包含一个额外的随机指针 random，它可以指向链表中的任意节点或空节点。

要求实现链表的深拷贝。新链表中的每个节点都应是全新节点，且 next 和 random 指针指向的也是新链表中的节点，并保持与原链表相同的结构。

哈希表法

首先克隆链表所有节点，同时使用哈希表记录新旧节点的对应关系，然后根据哈希表完成 random 指针的连接。

原地修改法

将每个副本插在原节点之后，则原节点 p 的副本是 p->next，其随机目标的副本是 p->random->next（目标非空时）。连接随机指针后，拆出副本链表并恢复原链表。算法仍需分配 nn 个输出节点，但除此之外只需 O(1)O(1) 辅助空间；处理期间会暂时修改原链表。

上次更新: