面试题：C++双向链表指针的复杂应用

双向链表结构设计

class DoubleNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

归并排序实现

def get_middle(head):
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def merge(l1, l2):
    dummy = DoubleNode(0)
    tail = dummy
    while l1 and l2:
        if l1.value <= l2.value:
            tail.next = l1
            l1.prev = tail
            l1 = l1.next
        else:
            tail.next = l2
            l2.prev = tail
            l2 = l2.next
        tail = tail.next
    if l1:
        tail.next = l1
        l1.prev = tail
    if l2:
        tail.next = l2
        l2.prev = tail
    new_head = dummy.next
    new_head.prev = None
    return new_head


def merge_sort(head):
    if not head or not head.next:
        return head
    mid = get_middle(head)
    right_half = mid.next
    mid.next = None
    right_half.prev = None
    left = merge_sort(head)
    right = merge_sort(right_half)
    sorted_list = merge(left, right)
    return sorted_list

指针在操作中的作用

寻找中间节点：在get_middle函数中，使用快慢指针。slow指针每次移动一步，fast指针每次移动两步。当fast指针到达链表末尾时，slow指针指向的就是链表的中间节点。这是为了将链表分成大致相等的两部分，为归并排序做准备。
分割链表：在merge_sort函数中，找到中间节点mid后，将链表从中间断开，mid.next = None，并将right_half的前驱指针置空right_half.prev = None，这样就得到了两个独立的子链表。
合并链表：在merge函数中，通过比较两个子链表当前节点的值，将较小值的节点接到结果链表的tail后面。移动指针时，不仅要更新next指针，也要同时更新prev指针，以维持双向链表的结构。例如，tail.next = l1，同时l1.prev = tail。

时间复杂度分析

归并排序的时间复杂度遵循递归关系：$T(n) = 2T(\frac{n}{2}) + O(n)$。其中$2T(\frac{n}{2})$表示对两个子链表进行排序的时间，$O(n)$表示合并两个子链表的时间。根据主定理，时间复杂度为$O(n log n)$，$n$是链表的长度。

空间复杂度分析

空间复杂度主要来自递归调用栈。在最坏情况下，递归深度为$log n$，每层递归需要$O(1)$的额外空间，所以空间复杂度为$O(log n)$。

星途面试题库