今日算法之_55_旋转链表
前言
Github:https://github.com/HealerJean
1、旋转链表
给定一个链表,旋转链表,将链表每个节点向右移动 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、解题思路
1、首先需要明确一点,为了不做无用功,我们需要知道 k如果和链表的个数相同则旋转之后不变 。 也就是说k的个数应该如下
//如果k比较大,甚至是head长度的倍数的时候,其实相等于会重复走,所以我们直接取不重复的移动
if (k == nodeCount){
return listNode;
}else if (k > nodeCount){
k = k % nodeCount;
}
2、遍历链表,直到倒数第二个,以链表1->2->3->4->5->NULL
为例。倒数第二个节点4将会是终点,4.next = 5 将会使第一个节点,我们首先就需要将4这个节点定位。然后将首个节点放到5的后面,接着5作为头。4作为尾、具体看下面的代码吧
1.2、算法
public class 旋转链表 {
@Test
public void test(){
ListNode listNode = listNode();
printListNode(listNode);
listNode = rotateRight(listNode, 1);
printListNode(listNode);
}
public ListNode rotateRight(ListNode head, int k) {
//极端情况
if (head == null){
return null;
}
if (k == 0){
return head;
}
//节点数
ListNode listNode = head;
int nodeCount = 0 ;
while (head != null) {
nodeCount++;
head = head.next;
}
//如果k比较大,甚至是head长度的倍数的时候,其实相等于会重复走,所以我们直接取不重复的移动
if (k == nodeCount){
return listNode;
}else if (k > nodeCount){
k = k % nodeCount;
}
//开始真正的 旋转
return rotateRightMethod(listNode,k);
}
public ListNode rotateRightMethod(ListNode head, int k){
if (k == 0){
return head;
}
//取出第一个节点,因为第一个节点要放到后面去
ListNode firstNode = head;
//因为最后一个节点要移动到首个节点,这里我们需要渠道倒数第二个节点,因为倒数第二个节点将会作为最后一个节点
while (head.next.next != null){
ListNode next = head.next ;
head = next;
}
//head此时为倒数第二个节点
head.next.next = firstNode;
ListNode node = head.next;
head.next = null;
node = rotateRight(node, k-1);
return node;
}
void printListNode(ListNode listNode){
while (listNode != null){
System.out.printf( listNode.value + ",");
listNode = listNode.next;
}
System.out.println();
}
public ListNode listNode(){
ListNode listNode_5 = new ListNode(5, null);
ListNode listNode_4 = new ListNode(4, listNode_5);
ListNode listNode_3 = new ListNode(2, listNode_4);
ListNode listNode_2 = new ListNode(1, listNode_3);
ListNode listNode_1 = new ListNode(0, listNode_2);
return listNode_1;
}
}
class ListNode{
int value ;
ListNode next ;
public ListNode(int value, ListNode next) {
this.value = value;
this.next = next;
}
}
1.3、测试
@Test
public void test(){
ListNode listNode = listNode();
printListNode(listNode);
listNode = rotateRight(listNode, 1);
printListNode(listNode);
}