1.1. 题目

1.1.1. 合并K个排序链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

1.1.2. 题解:

• 旋转链表,把链表向右移动k个位置,此时可以理解链表头尾相连
• 不管移动多少,链表里的个数不会变,而且仔细看,类似把链表分了块,用其中一块做头,另外一块接在后面

1.1.3. 思路:

• 仔细观察,当k等于链表长度的时候,移动后的结果跟原链表是一样的!
• 当k==1时,链表整体往右移动一个,可以理解为把原末尾节点放到头节点,原倒数第二节点指向nil
• 比如 1->2->3->4->5->NULL, k = 2 可以理解为 4->5,1->2->3,把5下一个节点指向1,原3节点的下一个节点指向nil
• 仔细发现关系就是 链表长度 - ( k % 链表长度 ) 处开始拆分链表,把后面的链表放到前面,前面的放到后面

1.1.4. 代码:

 func rotateRight(head *ListNode, k int) *ListNode {

     if head == nil || head.Next == nil {
         return head
     }

     lens,lastNode := listLen(head)
     if lens == k {
         return head
     }

     s := k % lens
     if s == 0 {
         return head
     }
     old := head
     for i:=0;i<lens-s-1;i++ {
         head = head.Next
     }

     newHead := head.Next
     lastNode.Next = old
     head.Next = nil
     return newHead
 }
 func listLen(head *ListNode) (int,*ListNode) {
     i := 1
     for head.Next != nil {
         i++
         head = head.Next
     }
     return i,head
 }

代码