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->널. 그러나 문제에는 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줄을 끝에서 끝까지 연결하는 기술로, 작업량을 대폭 절약할 수 있다는 점입니다. 실제로 이전 아이디어에서 설명한 단계를 따르기만 하면 문제가 없습니다. 하지만 이 기술은 정말 훌륭하고 배울 가치가 있습니다. 코드 주석에 구체적인 내용을 썼습니다.

읽어주셔서 감사합니다. 도움이 되기를 바랍니다. 이 사이트를 지원해 주셔서 감사합니다!

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