【每日一题】- 2020-xx-xx - xxx

[RealDuxy]

题目名称

旋转链表

题目链接

题目链接

题目思路

拆解链表，重新拼接，重点在于找到断点以及拼接操作

题目代码

# 这里写下解决问题的Python代码
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0: return head
        
        # 特殊情况直接得到答案
        total_length = 1
        node = head
        while node.next:
            # print(node.next.val)
            node = node.next
            total_length += 1
        print("final total length: ", total_length)

        if k == total_length:
            return head
        if k > total_length:
            k = k % total_length
        print("final k: ", k)

        if k == 0:
            return head

        # 本质上是找到断点，然后将断电后的链表移位
        peak_node = head
        for _ in range(total_length-k-1):
            peak_node = peak_node.next
        print(peak_node.val)

        post_peak_node = peak_node.next
        new_head = post_peak_node
        print(k)
        for _ in range(k-1):
            post_peak_node = post_peak_node.next
            print(post_peak_node.val)

        post_peak_node.next = head
        peak_node.next=None

        return new_head

## 复杂度