Question

假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

Answer 1

问：假设长度大于1的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点

答：本题需要先找到待删除结点的前驱结点，然后再进行删除操作。由于链表是循环的，所以需要特别处理头结点和尾结点。算法流程如下：1. 如果链表只有两个结点，p所指的结点为尾结点，则直接删除头结点，并把尾结点指向新的头结点；否则直接删除头结点。2. 如果链表有三个及以上结点，先找到待删除结点的前驱结点pre。处理pre时，需要注意两个特殊情况： （1）如果p所指的结点为头结点，则需要先找到尾结点，并把尾结点的next指向头结点的next，即新的头结点。此时pre指向尾结点，即p的前驱结点。 （2）如果p所指的结点为尾结点，则需要先找到头结点，并把头结点的next指向尾结点的next，即新的尾结点。此时pre指向p的前驱结点。3. 判断pre是否为空，如果为空，则p所指的结点既没有前驱结点，也没有后继结点（链表只有两个结点），无法完成删除操作，直接返回。否则，找到pre的前驱结点prepre，并把prepre的next指向p，完成删除操作。

答：代码实现如下（假设链表中每个结点的数据类型为int）：```python# 删除p的前驱结点def delete_predecessor(p): if p is None or p.next is None: return pre = p while pre.next != p: pre = pre.next if pre == p: # 遍历一圈回到p，表明链表中只有两个结点 pre = None break if pre is None: if p.next == p: # 删除后链表为空 p = None else: # 删除头结点 tail = p while tail.next != p: tail = tail.next

问：已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，编写算法求出 A 和 B 的交集 C ，要求 C 同样以元素递增的单链表形式存储。

答：好的

答：算法思路：1. 定义三个指针分别指向 A 链表、B 链表和 C 链表的开始节点，初始化这三个指针；2. 遍历 A 链表和 B 链表，在两个链表中都找到相同的节点，将该节点添加到 C 链表中；3. 如果 A 链表中节点的值小于 B 链表中节点的值，则将 A 链表的指针后移一位，否则将 B 链表的指针后移一位；4. 重复步骤 2 和步骤 3 ，直到遍历完其中一个链表。

答：算法实现：class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextdef getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode: if not headA or not headB: return None pA, pB, pC = headA, headB, None while pA and pB: if pA.val == pB.val: node = ListNode(pA.val) if pC: pC.next = node pC = pC.next else: pC = node

答：算法分析：- 时间复杂度：O(min(m,n))，其中 m 和 n 分别为两个链表的长度。最坏情况下，需要遍历完较短的链表，所以时间复杂度为 O(min(m,n))。- 空间复杂度：O(m+n)，其中 m 和 n 分别为两个链表的长度。需要创建一个新的链表存放交集的节点，所以空间复杂度为 O(m+n)。

问：设有一个双向链表，每个结点中除有 prior 、 data 和 next 域外，还有一个访问频度 freq 域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次 Locata ( L , x ）运算后，令值为 x 的结点中的 freq 域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的 Locata ( L , x ）算法。

答：1. 遍历整个链表，查找是否存在值为 x 的结点。2. 如果存在，则将该结点的 freq 域加1，并将该结点向前移动，直到其前面的结点的 freq 域的值小于等于它的 freq 域的值。3. 如果不存在，则在链表头部添加一个值为 x，freq 域为1的结点，然后将该结点向后移动，直到其后面的结点的 freq 域的值大于等于它的 freq 域的值。

答：具体实现代码如下：void Locata(Node *&L, int x) { Node *p = L; bool found = false; while (p != NULL) { if (p->data == x) { found = true; p->freq++; while (p->prior != NULL && p->freq > p->prior->freq) { // 交换当前结点和前面的结点 p->prior->next = p->next; if (p->next != NULL) p->next->prior = p->prior; p->next = p->prior; p->prior = p->next->prior;

答：p->next->prior = p; if (p->prior != NULL) p->prior->next = p; } break; } p = p->next; } if (!found) { Node *newNode = new Node; newNode->data = x; newNode->freq = 1; newNode->prior = NULL; newNode->next = L; if (L != NULL) L->prior = newNode; L = newNode; while (newNode->next != NULL && newNode->freq newNode->next->freq) {

答：// 交换当前结点和后面的结点 newNode->next->prior = newNode->prior; newNode->prior = newNode->next; newNode->next = newNode->prior->next; newNode->prior->next = newNode; if (newNode->next != NULL) newNode->next->prior = newNode; if (L == newNode->prior) L = newNode; } }}