/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcrotateRight(head *ListNode, k int) *ListNode {if k==0||head ==nil|| head.Next ==nil {return head } listHead :=make([]*ListNode, 0) l := headfor ; l !=nil; l = l.Next { listHead =append(listHead, l) } length :=len(listHead) k = k % lengthif k ==0 {return head } listHead =append(listHead[length-k:], listHead[:length-k+1]...) listHead[k-1].Next = listHead[k] listHead[length-1].Next =nilreturn listHead[0]}
复杂度分析一
时间复杂度: 只遍历了一遍链表,因此时间复杂度为 O(n),其中 n 是链表的长度
空间复杂度: 空间复杂度为 O(2n)
解题思路二
将链表头尾相连,组成环形链表
找到第length-k个节点,新的链表的head为该节点的Next,将该节点Next修正为nil
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcrotateRight(head *ListNode, k int) *ListNode {if k ==0|| head ==nil|| head.Next ==nil {return head } length :=1 l := headfor ; l.Next !=nil; l = l.Next { length++ } k = k % length add := length - k l.Next = headfor add >0 { l = l.Next add-- } res := l.Next l.Next =nilreturn res}