복붙노트

[PYTHON] 파이썬에서 링크 된 목록을 반대로한다.

PYTHON

파이썬에서 링크 된 목록을 반대로한다.

머리글이 링크 된 목록 인 경우, 머리글을 매개 변수로 사용하는 것을 역순으로 요청합니다. 예 : 이미 정의 된 함수에서 반환 된 1 -> 2 -> 3이 방법으로 함수 reverse_linked_list를 구현하려고했습니다.

def reverse_linked_list(head):
temp = head
head = None
temp1 = temp.next
temp2 = temp1.next
temp1.next = None
temp2.next = temp1
temp1.next = temp
return temp2
pass

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

def to_linked_list(plist):
head = None
prev = None
for element in plist:
    node = Node(element)
    if not head:
        head = node
    else:
        prev.next = node
    prev = node
return head

def from_linked_list(head):
result = []
counter = 0
while head and counter < 100: # tests don't use more than 100 nodes, so bail if you loop 100 times.
    result.append(head.value)
    head = head.next
    counter += 1
return result


def check_reversal(input):
    head = to_linked_list(input)
    result = reverse_linked_list(head)
    assert list(reversed(input)) == from_linked_list(result)

이 방법으로 호출됩니다 : check_reversal ([1,2,3]). 필자가 목록을 뒤집기 위해 작성한 함수는 [3,2,1,2,1,2,1,2,1]을 제공하고 길이가 3 인 목록에 대해서만 작동합니다. 어떻게 길이 목록으로 일반화 할 수 있습니까? 엔?

해결법

  1. ==============================

    1.U는 각 반복에 대해 나머지를 얻기 위해 mod 함수를 사용할 수 있으며 분명히 목록을 뒤집는 데 도움이 될 것입니다. 나는 네가 선교 R과 D에서 온 학생이라고 생각한다.

    U는 각 반복에 대해 나머지를 얻기 위해 mod 함수를 사용할 수 있으며 분명히 목록을 뒤집는 데 도움이 될 것입니다. 나는 네가 선교 R과 D에서 온 학생이라고 생각한다.

    head=None   
prev=None
for i in range(len):
    node=Node(number%10)
    if not head:
        head=node
    else:
        prev.next=node
    prev=node
    number=number/10
return head
  2. ==============================

    2.받아 들여진 대답은 존재하지 않는 것 (숫자, 노드, 함수가 아닌 숫자로서의 len)의 무리를 가리 키기 때문에 나에게 어떤 의미가 없습니다. 이 숙제는 오래 전부터 나왔으므로 가장 효과적인 코드라고 생각합니다.

    받아 들여진 대답은 존재하지 않는 것 (숫자, 노드, 함수가 아닌 숫자로서의 len)의 무리를 가리 키기 때문에 나에게 어떤 의미가 없습니다. 이 숙제는 오래 전부터 나왔으므로 가장 효과적인 코드라고 생각합니다.

    이는 기존 목록 노드를 수정하는 파괴적인 반전을 수행하기위한 것입니다.

    def reverse_list(head):
    new_head = None
    while head:
        head.next, head, new_head = new_head, head.next, head # look Ma, no temp vars!
    return new_head

    기능을 덜 공상적으로 구현하면 하나의 임시 변수와 여러 개의 할당 문이 사용되므로 이해하기가 더 쉽습니다.

    def reverse_list(head):
    new_head = None  # this is where we build the reversed list (reusing the existing nodes)
    while head:
        temp = head  # temp is a reference to a node we're moving from one list to the other
        head = temp.next  # the first two assignments pop the node off the front of the list
        temp.next = new_head  # the next two make it the new head of the reversed list
        new_head = temp
    return new_head

    또 다른 디자인은 이전 버전을 변경하지 않고 완전히 새로운 목록을 만드는 것입니다. 목록 노드를 변경 불가능한 객체로 취급하려는 경우에 더 적합합니다.

    class Node(object):
    def __init__(self, value, next=None): # if we're considering Nodes to be immutable
        self.value = value                # we need to set all their attributes up
        self.next = next                  # front, since we can't change them later

def reverse_list_nondestructive(head):
    new_head = None
    while head:
        new_head = Node(head.value, new_head)
        head = head.next
    return new_head
  3. ==============================

    3.Blckknght의 대답이 유용하다는 것을 알았지 만 그것은 정확 합니다만 실제로 어떤 일이 일어나고 있는지 이해하기 위해 애썼지 만 주로 Python의 구문에 따라 두 변수를 한 행으로 교체 할 수있었습니다. 변수 이름도 약간 혼란 스럽습니다.

    Blckknght의 대답이 유용하다는 것을 알았지 만 그것은 정확 합니다만 실제로 어떤 일이 일어나고 있는지 이해하기 위해 애썼지 만 주로 Python의 구문에 따라 두 변수를 한 행으로 교체 할 수있었습니다. 변수 이름도 약간 혼란 스럽습니다.

    이 예제에서는 이전, 현재, 다음을 사용합니다.

          def reverse(head):

        current = head
        previous = None

       while current:
         next = current.next
         current.next = previous   # None, first time round.
         previous = current        # Used in the next iteration.
         current = next            # Move to next node.

       head = previous

    예를 들어 3 개의 노드 (머리 = n1, 꼬리 = n3)로 단일 링크 된 목록을 봅니다.

    n1 → Na → Na

    while 루프를 처음 입력하기 전에 머리글 앞에 노드가 없으므로 previous는 None으로 초기화됩니다 (n1).

    나는 변수가 이전, 현재, 다음으로 링크 된리스트를 따라 움직이는 것을 항상 상상해 보는 것이 유용하다는 것을 발견했다.

    첫 번째 반복

    이전 = 없음

    [n1] -> [n2] -> [n3]  현재 다음  current.next = 이전

    두 번째 반복

    [n1] -> [n2] -> [n3]  이전 현재 다음                              current.next = 이전

    세 번째 반복

    # next is None

    [n1] -> [n2] -> [n3]                              이전 전류                                                          current.next = 이전

    현재 while == None 일 때 while 루프가 종료되므로리스트의 새로운 헤드는 우리가 마지막으로 방문한 노드 인 previous로 설정되어야합니다.

  4. ==============================

    4.목록을 '제자리에'되돌릴 수 있습니다. 이것은 일정 시간 O (n)에서 실행되고 제로의 추가 공간을 사용합니다.

    목록을 '제자리에'되돌릴 수 있습니다. 이것은 일정 시간 O (n)에서 실행되고 제로의 추가 공간을 사용합니다.

    def reverse(head):
  if not head:
    return head
  h = head
  q = None
  p = h.next
  while (p):
    h.next = q
    q = h
    h = p
    p = h.next
  h.next = q
  return h

    다음은 실행중인 알고리즘을 보여주는 애니메이션입니다. (#은 애니메이션 목적으로 Null / None을 나타냄)

  5. ==============================

    5.대화 형 python.org에서 빌린 노드 클래스 파트 : http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

    대화 형 python.org에서 빌린 노드 클래스 파트 : http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

    나는 역전 된 함수를 만들었습니다. 역순 루프의 모든 주석은 1 회 루핑을 의미합니다. 그런 다음 계속됩니다.

    class Node():
  def __init__(self,initdata):
    self.d = initdata
    self.next = None

  def setData(self,newdata):
    self.d = newdata

  def setNext(self,newnext):
    self.next = newnext

  def getData(self):
    return self.d

  def getNext(self):
    return self.next

class LinkList():
  def __init__(self):
    self.head = None

  def reverse(self):
    current = self.head   >>> set current to head(start of node)
    previous = None       >>>  no node at previous
    while current !=None: >>> While current node is not null, loop
        nextt =  current.getNext()  >>> create a pointing var to next node(will use later)
        current.setNext(previous)   >>> current node(or head node for first time loop) is set to previous(ie NULL), now we are breaking the link of the first node to second node, this is where nextt helps(coz we have pointer to next node for looping)
        previous = current  >>> just move previous(which was pointing to NULL to current node)
        current = nextt     >>> just move current(which was pointing to head to next node)

    self.head = previous   >>> after looping is done, (move the head to not current coz current has moved to next), move the head to previous which is the last node.
  6. ==============================

    6.나는 LList의 반전에서 다른 접근법을 시도했다. 주어진리스트 1,2,3,4

    나는 LList의 반전에서 다른 접근법을 시도했다. 주어진리스트 1,2,3,4

    주변 노드를 연속적으로 바꾼다면 솔루션을 얻을 수 있습니다.

    len=3 (size-1)
2,1,3,4
2,3,1,4
2,3,4,1

len=2 (size-2)
3,2,4,1
3,4,2,1

len=1 (size-3)
4,3,2,1

    아래의 코드는 그렇게합니다. Outer for 루프는 목록의 len을 연속적으로 줄여서 교환합니다. while 루프는 노드의 데이터 요소를 서로 바꿉니다.

    def Reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next


    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.data, temp.next.data = temp.next.data, temp.data
            temp = temp.next
            xcount += 1
    return head

    이것은 다른 솔루션만큼 효율적이지는 않지만 다른 관점에서 문제를 보는 데 도움이됩니다. 희망이 당신이 유용하다고 생각합니다.

  7. ==============================

    7.여기 한 표에 모든 것이 있습니다. 연결된 목록을 생성하고 역순으로 코드를 포함합니다.

    여기 한 표에 모든 것이 있습니다. 연결된 목록을 생성하고 역순으로 코드를 포함합니다.

    예제를 포함하여 유휴 .py 파일에 복사하여 붙여 넣기 만하면됩니다.

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


def reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next
    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.value, temp.next.value = temp.next.value, temp.value
            temp = temp.next
            xcount += 1
    return head


def printnodes(n):
    b = True
    while b == True:
        try:
            print n.value
            n = n.next
        except:
            b = False

n0 = Node(1,Node(2,Node(3,Node(4,Node(5,)))))
print 'Nodes in order...'
printnodes(n0)
print '---'
print 'Nodes reversed...'
n1 = reverse(n0)
printnodes(n1)
  8. ==============================

    8.

    def reverseLinkedList(head):

    current =  head
    previous = None
    nextNode = None

    while current:

        nextNode = current.nextNode
        current.nextNode = previous

        previous = current
        current = nextNode

    return previous

    9. from https://stackoverflow.com/questions/21529359/reversing-a-linked-list-in-python by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] Mac OS X 10.10.2에서 python six 패키지를 업그레이드 할 수 없습니다.  (0) 2018.11.07
[PYTHON] 코드 효율성 향상 : 슬라이딩 윈도우의 표준 편차  (0) 2018.11.07
[PYTHON] scipy.integrate.ode에 적응 단계 크기 사용  (0) 2018.11.07
[PYTHON] 셸 명령에서 파이썬 스크립트로 파이프 출력  (0) 2018.11.07
[PYTHON] 판다에있는 문자열 목록이있는 str.contains를위한 확장 가능한 솔루션  (0) 2018.11.07
,

티스토리툴바