当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--13--旋转链表(Java)
(题目来源：力扣（LeetCode）)
示例 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
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//链表为空直接返回null
if(head==null){
return null;
}
//如果链表长度为1直接返回head
if(head.next==null){
return head;
}
//获取链表的长度
ListNode temp=head;
int count=1;
while(temp.next!=null){
temp=temp.next;
count++;
}
//循环k%count,获取将链表每个节点向右移动 k 个位置的链表
for(int i=0;i<k%count;i++){
//获取倒数第二个节点
ListNode tail=head;
while(tail.next.next!=null){
tail=tail.next;
}
//倒数第二个节点的下一节点等于头节点
tail.next.next=head;
//头节点等于倒数第二个节点
head=tail.next;
//再将尾节点置为null
tail.next=null;
}
return head;
}
}
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// head=null->直接返回null
if (head == null) return null;
//如果链表长度为1，直接返回这个链表
if (head.next == null) return head;
// new一个尾节点
ListNode old_tail = head;
//记录链表长度
int n;
//循环完后n为链表长度，old_tail=尾节点
for(n = 1; old_tail.next != null; n++)
old_tail = old_tail.next;
//将链表拼接成循环链表
old_tail.next = head;
// 新尾节点 new_tail : 第(n - k % n - 1)个节点
// 新头节点 new_head : 第(n - k % n)个节点
ListNode new_tail = head;
//循环获取新的尾节点
for (int i = 0; i < n - k % n - 1; i++)
new_tail = new_tail.next;
//新尾节点的下一个节点就是新节点
ListNode new_head = new_tail.next;
//将链表断开，形成新的单向链表
new_tail.next = null;
return new_head;
}
}
class Solution {
public ListNode rotateRight(ListNode head, int k) {
//链表为空直接返回null
if(head==null) return null;
//链表为长度为1直接返回这个链表
if(head.next==null) return head;
//第一个指针
ListNode firstNode=head;
//第二个指针
ListNode seconedNode=head;
//用一个临时变量确定链表长度
ListNode temp=head;
int n=1;
while(temp.next!=null){
temp=temp.next;
++n;
}
//将第一个指针指向第k+1个节点
for(int i=0;i<k%n;i++){
firstNode=firstNode.next;
}
//两个指针同时移动，直到第一个指针指向最后一个节点
while(firstNode.next!=null){
firstNode=firstNode.next;
seconedNode=seconedNode.next;
}
//将链表拼接成环形链表
firstNode.next=head;
//此时seconedNode是新链表的尾节点
//new一个新头节点指向seconedNode.next
ListNode newHead=seconedNode.next;
//将环形链表断开形成新链表
seconedNode.next=null;
return newHead;
}
}
