Python 데이터 구조의 회전 링크

제목 설명:하나의 링크 를 지정 하고 링크 를 회전 시 켜 모든 노드 가 오른쪽으로 k 개의 위 치 를 이동 하 게 합 니 다.그 중에서 k 는 마이너스 가 아 닙 니 다.
샘플:링크 1->2->3->4->5->null 과 k=2 를 드 립 니 다.귀환 4->5->1->2->3->null
먼저,이 문제 가 달성 하고 자 하 는 목적 을 살 펴 보 자.사실은 다른 표현 으로 이렇게 묘사 할 수 있다.k 수 치 를 제시 하고 링크 를 마지막 k 개 노드 에서 시작 한 부분 을 링크 앞으로 이동 시 키 는 것 이다.예 를 들 어 4->5 이 부분 을 전체 링크 앞으로 이동 시 켜 4->5->1->2->3->null 로 바 꾸 는 것 이다.그러나 주의해 야 할 것 은 문제 에서 k 의 크기 를 제시 하지 않 았 다 는 것 이다.k 가 링크 의 길이 보다 더 클 때 우 리 는 먼저 k 로 링크 의 길 이 를 구 해 야 한다.예 를 들 어 k=7 이 라면 위의 예 는 4->5 를 전체 링크 앞으로 이동 해 야 한다.
그 러 니까 이 문제 의 사고방식 은 이렇게 요약 할 수 있다.
1.전체 링크 의 길 이 를 구 합 니 다.
2.k 값 에 따라 이동 해 야 할 부분 링크 의 전구(사례 중 3)를 찾 습 니 다.
3.앞 구 리 를 끊 고 뒤쪽 으로 이동
코드 는 다음 과 같 습 니 다:

# Definition for singly-linked list. 
# class ListNode: 
#   def __init__(self, x): 
#     self.val = x 
#     self.next = None 
 
class Solution: 
  # @param head: the list 
  # @param k: rotate to the right k places 
  # @return: the list after rotation 
  def rotateRight(self, head, k): 
    if head is None: 
      return head 
    cur = head 
    count = 1 
    #        
    while cur.next: 
      cur = cur.next 
      count += 1 
    #       ,            :          
    cur.next = head 
    #   ,k cur                   
    k = count - k % count 
    #      
    while k != 0: 
      cur = cur.next 
      k -= 1 
    #    
    head = cur.next 
    cur.next = None 
    #         ,                 ,     head 
    return head 
    # write your code here 
주의해 야 할 것 은 21 줄 의 앞 뒤 가 연 결 된 기교 이다.이것 은 우리 의 코드 양 을 크게 절약 했다.사실은 이전의 사고방식 에서 묘사 한 한 걸음 한 걸음 으로 해도 문제없다.하지만 이 기 교 는 정말 훌륭 해서 배 울 만하 다.구체 적 인 세부 사항 을 나 는 코드 주석 에 썼 다.
읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!

좋은 웹페이지 즐겨찾기