0

Я застрял на применении односвязного списка. Проблема в том, что я не могу понять почему не меняются местами последний и предпоследние элементы списка.

class LinkedListNode:

def __init__(self, value: object, next_: None):
    self.value = value
    self.next_ = next_

class LinkedList:

"""
front - первый нод в списке
back - последний
size - размер, если больше 0
"""

def __init__(self) -> None:

    self.front = None
    self.back = None
    self.size = 0

def prepend(self, value):
    """
    Помещаем элемент в начало списка.

    >>> lnk = LinkedList()
    >>> lnk.prepend(0)
    >>> lnk.prepend(1)
    >>> print(lnk)
    1 -> 0 -> |
    """
    self.front = LinkedListNode(value, self.front)
    if self.back is None:
        self.back = self.front
    self.size += 1


def swap_front_back(self):
    """
    Меняем LinkedListNodes front и back для связного списка. 
   Не меняя значения и не создавая еще один связной список.

    >>> lnk = LinkedList()
    >>> lnk.prepend(3)
    >>> lnk.prepend(2)
    >>> lnk.prepend(1)
    >>> print(lnk)
    1 -> 2 -> 3 -> |
    >>> front_id = id(lnk.front)
    >>> back_id = id(lnk.back)
    >>> lnk.swap_front_back()
    >>> print(lnk)
    3 -> 2 -> 1 -> |
    >>> front_id == id(lnk.back)
    True
    >>> back_id == id(lnk.front)
    True
    """
    # Код нерабочий черновик

    element = self.front

    element.next = tmp.next

    while element.next != self.back:
        if element.next == self.back:
           element.next = element
    self.back.next = element.next
5
  • Вы хотите поменять местами последний и предпоследний элементы связного списка?
    – jfs
    6 июн 2018 в 14:23
  • связанный вопрос: развернуть связный список на python
    – jfs
    6 июн 2018 в 14:24
  • Здравствуйте! Что-то вроде того, но меняя определенные ноды! Как например : 1-2-3-4-5, после swap 5-2-3-4-1.
    – TicTac
    6 июн 2018 в 18:15
  • вы хотите поменять значения первого и последнего узлов или сами узлы?
    – jfs
    6 июн 2018 в 18:23
  • Сами узлы, не меняя значения. При значениях это легко сделать, но не меняя я залип на этой проблеме.
    – TicTac
    6 июн 2018 в 18:31

1 ответ 1

0

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

  1. меньше двух узлов: вернуть список как есть
  2. ровно два узла: поменять узлы местами
  3. больше двух: сделать, чтобы последний узел указывал бы на второй узел, а предпоследний — на первый.
def swap_first_last(head):
    if head and head.next: # at least two nodes
        ntl = next_to_last(head)
        last = ntl.next
        if ntl is head:  # exactly two nodes
            last.next, head.next, head = head, last.next, last
        else: # > 2
            last.next, head.next, ntl.next, head = head.next, last.next, head, last
    return head

где next_to_last() ищет предпоследний узел:

def next_to_last(head):
    if not head or not head.next:
        raise ValueError("can't return the next to last node: the llist is too short")
    while head.next:
        node, head = head, head.next
    return node

Пример:

>>> print_list((Node(1, Node(2, Node(3, Node(4))))))
1 -> 2 -> 3 -> 4
>>> print_list(swap_first_last(Node(1, Node(2, Node(3, Node(4))))))
4 -> 2 -> 3 -> 1

где print_list() и Node определены в ответе на похожий вопрос.

Это достаточно прямолинейное решение в лоб, возможно есть более элегантный подход.

1
  • Спасибо! Я сделал не вводя дополнительное значение, через loop, while self.front is not None. Спасибо еще раз за дополнительные варианты.
    – TicTac
    7 июн 2018 в 17:09

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.