역순으로 목록을 역순으로 연결

Question

파이썬에서 링크 된 목록을 재귀 적으로 바꾸는 알고리즘에 문제가 있습니다.

def reverse(lis, prev = None): 
    if lis.next != None: 
     reverse(lis.next, lis) 
    lis.next = prev 

입력 : 3 1 4

출력 : 어떤 생각이 왜 3

작동하지 그것?

Answer 1

문제는 연결된 목록의 루트뿐만 아니라 변경된 것입니다 : 목록을 변경 한 후, 당신의 요소 3 실제로 마지막 요소이며, 함수 더 나은 반환 루트뿐만 아니라 :

def reverse(lis, prev = None): 
    if lis.next != None: 
     temp = lis.next 
     lis.next = prev 
     return reverse(temp, lis) 
    else: 
     return lis # the new root 

그래서 지금 당신은 그것을 전화 :

oldroot = ... #construct linked list 
newroot = reverse(oldroot) 
print(newroot) 

그래서 함수가 정확하지만 수술 후 당신의 손에 잘못 연결리스트 요소를 가지고있다.

Answer 2

이 일부 함수형 프로그래밍 연습처럼 보이는, 그래서 나는 당신에게 기능 솔루션 (그것을 복사 목록) 현재 : 대신 새 체인을 만드는 대신에

def reverse(link, rest=None): 
    if link is None: 
     return rest 
    return reverse(link.next, LinkedList(link.value, rest)) 

class LinkedList: 
    def __init__(self, value=None, next=None): 
     self.next = next 
     self.value = value 
    def print(self): 
     print(self.value) 
     if self.next is not None: 
      self.next.print() 

def to_linked_list(items): 
    if len(items) == 0: 
     return None 
    return LinkedList(items[0], to_linked_list(items[1:])) 

to_linked_list([1, 2, 3, 4, 5]).print() 
# 1, 2, 3, 4, 5 
reverse(to_linked_list([1, 2, 3, 4, 5])).print() 
# 5, 4, 3, 2, 1 

Answer 3

:

def reverse_linked_list(node, prev=None): 
    if node.next is None: 
     node.next = prev 
     return node 
    root_node = reverse_linked_list(node.next, node) 
    node.next = prev 
    return root_node