By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

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);
}

​

ContactAuthor