题目
想法
题目如上图所示
根据题目，输入一个数字k ,使 链表 向右旋转 k 次，将得到一个新链表，然后将此链表返回。
复述一下旋转的过程
原有链表
旋转次数: 2
第一次旋转
第二次旋转
此链表就是我们的新链表
解决方法
想: 如果我们能够将最后一个节点拿到前面来，重复k次，不就能够解决该题目了么？
我们补充下Head 和 NULL 节点，再次来模拟一下旋转过程
该题目没有Head节点，Head节点指的是第一个节点
原始链表
旋转一次链表
注意到: 我们应该有3步操作
- 获取最后一个链表
- 将最后一个链表的下一个指针指向第一个链表
- 将倒数第二个链表的下一个指针指向NULL
以上方法重复k次，就可以解决该问题
伪代码
旋转伪代码
for (i=0;i<k;i++) last,end = getListLasts(head) //last: 获取倒数第二个链表数据 end: 获取倒数第一个链表数 end->next = head // 将倒数第一个链表数据的下一个节点指向 头节点 last->next = NULL // 将倒数第二个链表数据的下一个节点指向 NULL head = end // 将头结点指向旋转后的节点
获取最后的节点伪代码
curr = head while curr->next != NULL { last = curr // 记录倒数第二个 curr遍历下一个 }
解题
根据伪代码，我们顺利写出实际代码
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func rotateRight(head *ListNode, k int) *ListNode { if nil == head || nil == head.Next { return head } for i:=0;i<k;i++ { last , end := getListEnds(head) last.Next = nil end.Next = head head = end } return head } func getListEnds(head *ListNode) (*ListNode,*ListNode) { var curr *ListNode var last *ListNode curr = head for curr.Next != nil { last = curr curr = curr.Next } return last,curr }
提交之后，超出时间限制。。。。
重新思考循环
如报错所示，循环 200000... 次的确很恐怖，
不过发现如下规则
循环的次数的效果 == k % (链表长度)
即: 循环 2000000000 次，等同于 2000000000 % 3 (链表长度) == 2 次，实际选择2次即可
重新提交代码
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func rotateRight(head *ListNode, k int) *ListNode { // fmt.Println(listLen(head)) if nil == head || nil == head.Next { return head } for i:=0;i<(k%listLen(head));i++ { last , end := getListEnds(head) last.Next = nil end.Next = head head = end } return head } // 获取链表长度 func listLen(head *ListNode) int { i := 0 var curr *ListNode curr = head for curr != nil { i++ curr = curr.Next } return i } // 获取最后一个节点 和 倒数第二个节点 func getListEnds(head *ListNode) (*ListNode,*ListNode) { var curr *ListNode var last *ListNode curr = head for curr.Next != nil { last = curr curr = curr.Next } return last,curr }
思考
该题目考验的是对链表的熟悉程度，只要熟悉链表，一般就能解决问题，解决的方法不止一个，我通常的做法是，先使用暴力破解，尝试是否能够正常解决此问题，然后再对暴力破解进行分析，顺带看看能不能优化该算法。
