24. Поменяйте местами узлы в связанном списке попарно

LeetCode

Учитывая связанный список, поменяйте местами соседние узлы два на два и верните замененный связанный список. Вы не можете просто изменить значение внутри узла, вам нужно фактически выполнить обмен узлом.

image.png

输入：head = [1,2,3,4]
输出：[2,1,4,3]

Решение первое

повторятьПрежде чем отвечать, посмотрите сами, что делать. Основная идея: вынуть два узла по очередиnode1, node2, после обмена пустьnode1изnextнаправлениеnode2Дочерние узлы и, наконец, объединены вместе за целевым связанным списком.

def swapPairs1(head):

    # 特殊判断
    if head is None: return None
    if head.next is None: return head

    dummy = point = ListNode()  # 声明头结点和构建链表的节点

    def swapTwoNodes(node1, node2, point):
        """交换两个节点位置，并拼接在结果链表后面"""
        n2_next = node2.next
        point.next = node2
        node2.next = node1
        node1.next = n2_next  # 将交换后的node1的next指向 node2的子节点

    while head is not None:
        if head.next:  # 如果 head.next 不为空，就交换 head 和 head.next
            if point.next is not None:  # 如果 point.next 不为空，就将节点指向下下级节点，用于拼接后面交换的节点
                point = point.next.next
            swapTwoNodes(head, head.next, point)
            head = head.next  # 运行代码走一下就知道，head.next就是还没有被交换过的节点
        else:
            head = head.next  # 如果head.next为空，就直接指向next

    return dummy.next

Официальное написание:

def swapPairs2(head):
    """迭代，官方写法"""
    dummyHead = ListNode()
    dummyHead.next = head  # 创建哑节点，并指向head
    temp = dummyHead  # 每次需要交换 temp 后面的两个节点
    while temp.next and temp.next.next:
        node1 = temp.next
        node2 = temp.next.next
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        temp = node1  # temp 指向交换过后 node1 的位置
    return dummyHead.next
Анализ сложности
  • Временная сложность: O(n), где n — количество узлов в связанном списке. Необходимо обновить операцию указателя для каждого узла.
  • Пространственная сложность: O(1).

Решение второе

Обратитесь к официальному ответу Likou. Основная идея: узлы в связанном списке можно обменивать парами рекурсивным способом. Условие завершения рекурсии состоит в том, что в связанном списке нет ни одной вершины, или в связной списке есть только одна вершина, и обмен в это время не может быть выполнен.

def swapPairs3(head):
    """递归"""
    if not head or not head.next: return head  # 特殊值判断
    newhead = head.next  # 记录头结点的下一个节点
    head.next = swapPairs2(newhead.next)  # 将后面节点newhead.next的交换结果，作为head的next节点
    newhead.next = head  # 交换节点，将head作为newhead的next节点
    return newhead
Анализ сложности
  • Временная сложность: O(n), где n — количество узлов в связанном списке. Необходимо обновить операцию указателя для каждого узла.
  • Пространственная сложность: O(n), где n — количество узлов в связанном списке. Сложность пространства в основном зависит от пространства стека рекурсивных вызовов.

Официальный ответ Ликоу

Категории