61. Rotate List

23 Jan 61. Rotate List

Posted at 18:21h in Coding by
0 Likes

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109
 

解题思路

首先将将链表变成环，同时计算出一共有多少个结点，然后移动到(n-k%n-1)这个节点，其后一个节点为结果，并把这个节点的next指针变为空

代码

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next: 
            return head
        
        tail = head
        n = 1
        while head.next :
            head = head.next
            n += 1
        head.next = tail
        head = head.next
        
        for i in range(n - k % n - 1):
            head = head.next
        res = head.next
        head.next = None
        return res
https://maxming0.github.io/2020/10/07/Rotate-List/
 
 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        tail = head
        n = 1
        while head.next:
            head = head.next
            n += 1
       
        head.next = tail
        head = head.next
        k = n – k%n – 1
        for i in range(k):
            head = head.next
        result = head.next
        head.next = None
        return result
No Comments

Post A Comment