어떻게 파이썬에서 노드의 단일 링크 된 목록을 되돌릴 수 있습니까?

Question

코드 단편은 다음과 같습니다. 노드 목록을 역으로 만들려고 시도하지만 그렇게하면 링크 된 목록의 첫 번째 노드 만 인쇄됩니다. 내가 여기서 뭘 잘못하고 있는거야? 필자는 이것을 종이에 썼다. 내 노드를 통해 루프를 돌면서 각각을 새로운 링크드 목록에 추가하는 것처럼 보인다. newList.head.next = temp : 문제의

# node class 
class Node(object): 
    def __init__(self, value, next=None): 
     self.value = value 
     self.next = next 

# singly linked list class 
class SinglyLinkedList(object): 
    def __init__(self): 
     self.head = None 
     self.tail = None 

# I'm trying to do the same thing in my reverseList() method 
# as I'm doing in the addFront method 
def addFront(self, value): 
    # create new node 
    newNode = Node(value) 
    # set old head to point to new node 
    if self.head == None: 
     self.head = newNode 
     self.tail = newNode 
    else: 
     # store old head 
     last_head = self.head 
     # set head to new node 
     self.head = newNode 
     # point head to old head 
     self.head.next = last_head 

# reverseList() method not working? 
# Only giving me first head value? Why? 
def reverseList(self): 
     node = self.head 
     newList = SinglyLinkedList() 
     newList.head = None 
     while node: 
      if node.next == None: 
       break 
      else: 
       temp = newList.head 
       newList.head = node 
       newList.head.next = temp 
       print newList.head.value 
       node = node.next 

Answer 1

당신의 코드로 인해 당신이 node == node.next을 설정하는리스트의 마지막 요소를 건너 뛰는 것 같습니다 및 묻습니다 node.next에 값이 있습니다. 새 목록은 기존 목록의 노드를 다시 사용하여 개체를 공유하게합니다. 한 목록의 노드를 변경하면 다른 목록이 변경되므로 원하는 동작이 될 가능성이 없습니다. 특히 그 중 하나에 새 요소를 추가하면 목록이 이상하게 작동하는 것을 경험하게됩니다.

다음 코드는 원래 목록의 값이 역순으로 포함 된 새 목록을 만듭니다.

def revers(self): 
    rev = SinglyLinkedList() 
    node = self.head 

    while node: 
     newNode = Node(node.value) 
     if not rev.tail: 
      rev.tail = newNode 
     newNode.next = rev.head 
     rev.head = newNode 
     node = node.next 

    return rev 

다음 코드는 목록을 뒤집습니다.

def revers(self): 
    prev = self.head 
    next = self.head.next 
    prev.next = None 

    while next: 
     temp = next.next 
     next.next = prev 
     prev = next 
     next = temp 

    self.head, self.tail = self.tail, self.head 

코드에 대한 설명. 기능적 및 필수적 행동을 혼합하는 것은 일반적으로 나쁜 생각입니다. addFront 함수는 목록 개체를 수정하지만 요청한 역순 함수는 새 목록을 만듭니다. 모든 함수는 새 목록을 만들거나 현재 인스턴스를 수정해야합니다. 이렇게 혼합하면 목록의 동작을 예측하기가 매우 어려워집니다.

Answer 2

부분은 다음에 newList.head = node 할당 발생합니다. 첫 번째 줄은이 두 참조가 같은 것을 가리키게하고 다음 줄은 둘 다 바뀝니다 (이제는 서로 바꿔서 사용할 수 있기 때문에).

이

def reverseList(self): 
    node = self.head 
    newList = SinglyLinkedList() 
    newList.head = None 
    while node: 
     if node.next == None: 
      break 
     else: 
      temp = newList.head 
      newList.head = node 
      newList.tail = temp 
      print newList.head.value 
      node = node.next 

편집 : 새로운 노드 (객체)를 생성 괜찮다면 단지 포함하는

난 당신이 가서 당신이 당신의 새 목록의 꼬리에 이전 머리를 할당 할 필요가 있다고 생각 이전 노드 객체의 값 (나는 addFront가하고있는 생각입니다), 당신은 간단하게 교체 할 수 있어야한다 :

newList.head = node 

로

newList.head = Node(node.value, node.next) 

원래 게시물입니다.

우리는 참조 방문을 위해 재귀 함수

def reverse (item, tail = None): 
    next = item.next 
    item.next = tail 
    if next is None: 
     return item 
    else: 
     return reverse(next, item) 

하여 목록을 되돌릴 수

Answer 3

: 다음 http://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/