2021-03-27：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。输入：head = 1→2→3→4→5, k = 2，输出：4→5→1→2→3。
福大大 答案2020-03-27：
1.找尾节点并且计算链表节点个数。
2.如果k大于等链表节点个数，需要取模，k一定在[0,节点个数)范围之内。如果k=0，直接返回头节点。
3.求倒数k+1的节点。
4.缓存倒数第k节点ans。
5.尾节点连头节点。
6.倒数k+1节点的Next指针为空。
7.返回ans。
代码用golang编写，代码如下：
package mainimport "fmt"func main() { head := &ListNode{Val: 1} head.Next = &ListNode{Val: 2} head.Next.Next = &ListNode{Val: 3} head.Next.Next.Next = &ListNode{Val: 4} printlnLinkNodeList(head) k := 6 fmt.Println("k =", k) fmt.Println("----------------") ret := rotateRight(head, k) printlnLinkNodeList(ret)}type ListNode struct { Val int Next *ListNode}func rotateRight(head *ListNode, k int) *ListNode { if head == nil { return head } //找尾节点并且计数 cnt := 1 tail := head for tail.Next != nil { cnt++ tail = tail.Next } k = k % cnt if k == 0 { //刚好是头节点，就不用操作了。 return head } //找倒数第k+1节点 fast := head slow := head k++ for k > 0 { fast = fast.Next k-- } for fast != nil { fast = fast.Next slow = slow.Next } //缓存结果 ans := slow.Next //尾节点连头节点 tail.Next = head //倒数k+1节点无Next指针 slow.Next = nil return ans}//链表打印func printlnLinkNodeList(head *ListNode) { cur := head for cur != nil { fmt.Print(cur.Val, "\t") cur = cur.Next } fmt.Println()}执行结果如下：
力扣61. 旋转链表
评论