python 알고리즘 문제 링크 반전 상세 설명

링크 의 반전 은 매우 흔 하고 기본 적 인 데이터 구조 문제 로 단 방향 링크 를 입력 하고 역순 으로 반전 한 링크 를 출력 한다.그림:위의 링크 는 아래 의 링크 로 전환 된다.링크 반전 을 실현 하 는 데 는 두 가지 방식 이 있 는데 하 나 는 순환 교체 이 고 다른 하 나 는 재 귀 이다.

첫 번 째 방식:나 쁜 것 을 따라 교체 한다.
나 쁜 교체 알고리즘 에 따라 세 개의 임시 변 수 를 필요 로 합 니 다.pre,head,next,임계 조건 은 링크 가 None 이거 나 링크 는 하나의 노드 만 있 습 니 다.

# encoding: utf-8
class Node(object):
def __init__(self):
self.value = None
self.next = None
def __str__(self):
return str(self.value)
def reverse_loop(head):
if not head or not head.next:
return head
pre = None 
while head:
next = head.next #            ，      
head.next = pre #          ，                      
pre = head #         （     ）    
head = next #         （  ）  
return pre #      ，              head  （    pre）

테스트 해 보기:

if __name__ == '__main__':
three = Node()
three.value = 3
two = Node()
two.value = 2
two.next = three
one = Node()
one.value = 1
one.next = two
head = Node()
head.value = 0
head.next = one
newhead = reverse_loop(head)
while newhead:
print(newhead.value, )
newhead = newhead.next

출력:

3
2
1
0
2

두 번 째 방식:귀속
재 귀적 사상 은:

head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
...

헤드 의 뒤쪽 지침 의 뒤쪽 지침 을 헤드 의 뒤쪽 지침 으로 바 꾸 어 유추 합 니 다.
실현 의 관건 적 인 절 차 는 임계 점 을 찾 아 언제 재 귀 에서 물 러 나 느 냐 하 는 것 이다.head.next 가 None 일 때 마지막 노드 임 을 설명 합 니 다.이 때 는 재 귀적 으로 호출 하지 않 습 니 다.

def reverse_recursion(head):
if not head or not head.next:
return head
new_head = reverse_recursion(head.next)
head.next.next = head
head.next = None
return new_head

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.