>  기사  >  백엔드 개발  >  Python 데이터 구조 뒤집힌 연결 목록

Python 데이터 구조 뒤집힌 연결 목록

高洛峰
高洛峰원래의
2017-02-28 09:24:391019검색

연결된 목록 뒤집기

예: 연결된 목록이 1->2->3->null인 경우 뒤집힌 연결 목록은 3-> ;2->1->null

비교적 간단한 방법은 "추출 방법"을 사용하는 것입니다. 즉, 먼저 새로운 빈 노드를 생성한 다음 전체 연결 목록을 순회하고 순회된 노드가 새로 생성된 연결 목록의 헤드 노드를 가리키도록 만듭니다.

예를 들어 단계는 다음과 같습니다.

1. 새 빈 노드 만들기: 없음
2->없음
3. .2->1->없음
4.3->2->1->없음

코드는 매우 간단합니다.

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

물론 조금 더 어려운 해결책이 있습니다. 연결 리스트에서 노드를 순서대로 선택하고 연결하는 방법에 대한 내부 플립 코드를 작성할 수 있습니다:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

고를 때, 빼낸 부분을 다시 연결하는 걸 잊지 마세요

읽어 주셔서 감사합니다. 모두에게 도움이 되었으면 좋겠습니다. 이 사이트를 지원해 주신 모든 분들께 감사드립니다!

Python 데이터 구조의 연결 목록 뒤집기와 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트에 주목하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.