XCPC Wiki

Appearance

链表 ​

在 XCPC 竞赛中，链表并不是常见的考点，因为链表对缓存（cache）不友好，几乎所有情况下我们都可以用 Map 或 Set 等类似数据结构来替代。

然而在面试场景中，链表却是常见题型，因为它可以实现面试官心目中的 O(1) 空间和 O(1) 时间操作，且一题往往有多种解法。

单链表模板 ​

定义如下：

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

插入节点：

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

删除节点：

cpp
void erase_next(Node *pre) {
  Node* tmp = pre->next;
  pre->next = tmp->next;
  delete tmp;
}
void erase(Node *p) {
  Node* tmp = p->next;
  p->value = tmp->value;
  p->next = tmp->next;
  delete tmp;
}

LeetCode 热门题目 ​

160. 相交链表 ​

题目链接

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

要求使用 O(1) 空间和 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 存储链表中的节点地址，然后遍历另一个链表查找。这种方式属于常规解法之一，如果面试官问有没有其他方法，记得回答这个。

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，判断该链表是否为回文链表。

递归法

首先找到链表中间节点，将后半部分反转，然后用两个指针分别从头和反转后的中间节点开始，逐一比较节点值是否相等。

cpp
bool isPalindrome(ListNode *head) {
  int n = 0;
  ListNode *p = head;
  while (p)
    ++n, p = p->next;
  p = head;
  for (int i = 0; i < (n + 1) / 2; ++i)
    p = p->next;
  auto *p2 = reverseList(p);
  p = head;
  while (p2) {
    if (p->val != p2->val)
      return false;
    p = p->next, p2 = p2->next;
  }
  return true;
}

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 判环法

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

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

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 个节点 ​

题目链接

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

双指针法

让一个指针先走 n 步，然后两个指针同步前进。当前指针到末尾时，另一个指针即指向待删除节点的前驱节点。

cpp
ListNode* removeNthFromEnd(ListNode* head, int n) {
  ListNode *p1 = head, *p2 = head;
  for (int i = 0; i < n; ++i)
    p1 = p1->next;
  if (p1) {
    while (p1->next)
      p1 = p1->next, p2 = p2->next;
    p2->next = p2->next->next;
    return head;
  } else {
    return head->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，每 k 个节点为一组进行翻转，返回修改后的链表。如果最后剩余节点不足 k 个，则保持原顺序。

Details

该实现过程较为复杂，需要多加练习与思考。

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. 随机链表的复制 ​

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

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

哈希表法

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

原地修改法

将新节点插入到原链表相应节点后方，这样可以在不额外开辟空间的情况下建立新旧节点之间的映射，实现深拷贝。具体实现略为复杂，需要仔细处理指针。