给你一个链表的头节点head旋转链表将链表每个节点向右移动k个位置。示例 1输入head [1,2,3,4,5], k 2输出[4,5,1,2,3]示例 2输入head [0,1,2], k 4输出[2,0,1]提示链表中节点的数目在范围[0, 500]内-100 Node.val 1000 k 2 * 10^9分析由于链表的长度可能小于k而旋转链表长度的整数倍后链表会恢复原状因此首先需要遍历一遍链表统计链表长度len同时记录链表的尾节点通过k % len得到真正有效的旋转次数避免重复旋转。之后将原链表的尾节点指向头节点使链表首尾相连形成一个环。因为旋转后的链表本质上从原链表的某个位置断开并重新选取一个新的头节点。因此只需要找到新的头节点和新的尾节点然后断开环即可完成旋转。对于向右旋转k个位置新的头节点应该是原链表中从头节点开始数第len - k个位置之后的节点。用dis (len - k) % len表示从原头节点出发需要移动的步数。随后从head开始向后移动dis步移动结束后指针p指向新的头节点指针q指向新的尾节点。最后将新的尾节点q的next指针置为空断开之前形成的环并返回新的头节点p。这样原链表后面的k个节点就被移动到了链表前面完成了链表的右旋操作。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* rotateRight(struct ListNode* head, int k) { if(!k||headNULL)return head; int len0,dis0; struct ListNode* phead,*qNULL; while(p!NULL) { qp,len,pp-next; } q-nexthead,kk%len,dis(len-k)%len,phead; for(int i0;idis;i) { qp,pp-next; } q-nextNULL; return p; }
