leetcode_61 旋轉連結串列

語言: CN / TW / HK

要求

給你一個連結串列的頭節點 head ,旋轉連結串列,將連結串列每個節點向右移動 k 個位置。

示例 1:

image.png 輸入:head = [1,2,3,4,5], k = 2 輸出:[4,5,1,2,3] 示例 2:

image.png 輸入:head = [0,1,2], k = 4 輸出:[2,0,1]

提示:

  • 連結串列中節點的數目在範圍 [0, 500] 內
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

核心程式碼

```python class ListNode: def init(self, val=0, next=None): self.val = val self.next = next

class Solution: def rotateRight(self, head: ListNode, k: int) -> ListNode: if head == None or head.next == None: return head prob = head counter = 1 while prob.next != None: counter += 1 prob = prob.next prob.next = head prob_new = head if k >= counter: k = k % counter for i in range(counter - k - 1): prob_new = prob_new.next new_head = prob_new.next prob_new.next = None return new_head ```

另一解法

```python class ListNode: def init(self, val=0, next=None): self.val = val self.next = next

class Solution: def rotateRight(self, head: ListNode, k: int) -> ListNode: if head == None: return head h = ListNode(-1) h.next = head prob = h prob1 = h counter = 0 while prob.next != None: counter += 1 prob = prob.next

    if k > counter:
        k = k % counter

    for i in range(counter - k):
        prob1 = prob1.next

    temp = prob1.next
    prob1.next = None

    prob2 = temp
    hh = ListNode(-1)
    hh.next = temp
    prob2 = hh
    while prob2.next != None:
        prob2 = prob2.next
    prob2.next = h.next
    return hh.next

```

image.png

解題思路:第一種解法:我們將我們的連結串列先變成一個圓環,然後我們數出來要在那個節點的位置斷開即可;第二種解法:我們直接找到要斷開的節點,將後面節點儲存起來,然後斷開節點後面是None,在遍歷到儲存節點的最後,然後將我們的頭節點接到我們的節點後面,完成旋轉操作。