[数据结构与算法]LC61.旋转链表

题目

查看题目

解题思路

初步的想法是定义两个链表，copy_list是初始链表的一个复制，因为本道题的想法是模拟一个环，但是直接定义环不现实。观察题目，第一个元素向右移动的时候，链表的末尾的元素会因为第一个元素的移动而被”挤“到前面来，当向右移动两个元素的时候，末尾的倒数两个元素会到前面来，这就考虑使用复制链来查找倒数第N个元素，找到后将找到的链连接到原始链中，然后将原始链中的倒数N个元素删除，完成操作。对于移动的步数，要先记录链表的长度，然后进行一次取余操作，获取最终的移动步数。
不出意外的话就一定会出意外，上面的初步想法果然有问题，我设想的用一条复制链其实在理论上是绝对可以实现的，但是我写的时候将新链指向head，实际上这根本不是一条新链，在所谓的”复制链”上的任何操作都会影响原始的head的链，这就是我为什么一直报空指针的错误了（因为将倒数第N位取走了，如果N超过N/2，就会导致原始的head链找不到倒数第N个元素，fast指针一定会跑到null.next中去，导致出现问题）也正是这个错误给了我启发，为何不直接在一条链上进行操作呢，直接将倒数第N个元素所在的链移动到head之前不不就齐活了，事实证明这样确实是可行的，除了上面这些点，其他思想和初步想法一样，包括定义一个连接指针，用来连接head（将找到的倒数第N个元素所在的链添加到头部位置），其实说白了这个题的核心就是：找倒数第N位元素+链表合并（最简单的合并）

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 //初步的想法是定义两个链表，copy_list是初始链表的一个复制，因为本道题的想法是模拟一个环，但是直接定义环不现实。观察题目，第一个元素向右移动的时候，链表的末尾的元素会因为第一个元素的移动而被”挤“到前面来，当向右移动两个元素的时候，末尾的倒数两个元素会到前面来，这就考虑使用复制链来查找倒数第N个元素，找到后将找到的链连接到原始链中，然后将原始链中的倒数N个元素删除，完成操作。对于移动的步数，要先记录链表的长度，然后进行一次取余操作，获取最终的移动步数。
class Solution {
    //查找倒数第N个元素

    public ListNode rotateRight(ListNode head, int k) {
        
        if(head==null) return null;
        if(head.next==null) return head;
        if(k==0) return head;
        //用来记录链表的长度
        int sum=0;
        ListNode sum_test=head;
        while(sum_test!=null){
            sum_test=sum_test.next;
            sum++;
        }
        // System.out.print(sum);
        //获取最终的移动步数
        int n=k%sum;
        if(n==0) return head;
        //定义链表的复制链表，找到倒数第N个元素，并进行断链操作
        ListNode summy=new ListNode(-1);
        ListNode copy_list=head;
        summy.next=copy_list;
        ListNode copy_fast=summy;
        ListNode copy_low=summy;
        ListNode copy_break=summy;
        int tmp=n;
        while(tmp!=0){
            copy_fast=copy_fast.next;
            tmp--;
        }
        while(copy_fast!=null){
            copy_low=copy_low.next;
            copy_fast=copy_fast.next;
        }//此时copy_low已经找到了倒数第N个元素起始的链表了
        //下面进行断链
        while(copy_break.next!=copy_low){
            copy_break=copy_break.next;
        }
        copy_break.next=null;//完成断链
        //定义连接指针，用来链接此链与原始链
        ListNode touch=copy_low;
    
        while(touch.next!=null){
            touch=touch.next;//找到链表中的最后一个元素并定位在这
        }
        //下面对原始链进行操作.
        //下面进行两个链表的拼接，由于复制链表定义的连接指针，这里直接连接指针直接指向summy_ori.next即可
        touch.next=summy.next;

        //返回copy_low
        return copy_low;
    }
}