面试手撕碰到的原题，分享下解答过程

旋转链表

问题描述

给你一个链表的头节点 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 \le Node.val\le 100
  • 0\le k \le 2*10^9

解题思路

首先我们需要通过遍历链表来确定链表长度len找到链表尾节点tail。

为了防止k超过链表长度，我们直接让k=k%n

既然是向右移动k个位置，我们以1->2->3->4->5为例，它向右移动两次后变成4->5->1->2->3,此时k=2，我们其实只需要找到第n-k(3这个节点)个位置，让n-k的下一个位置，也就是第n-k+1(4这个节点)个位置充当变换之后的头节点，然后把原数组的尾部节点(5)和头节点相连。最后把第n-k位置的节点和第n-k+1位置的节点脱链即可。
image-20231222172046401

代码实现

public class LeetCode61 {
    public ListNode rotateRight(ListNode head, int k) {
        if(k==0||head==null||head.next==null){
            return head;
        }
        int len=0;//链表长度
        ListNode p=head;
        ListNode tail=null;
        while(p!=null){//找到尾结点并求出链表长度
            len++;
            tail=p;
            p=p.next;
        }
        k=k%len;
        //找到第n-k个结点，1-n-k是链表前n-k个结点，n-k+1~n是后k个结点
        //然后将链表的后k个结点和前n-k个结点连接起来，让head指向新的头节点(原第n-k+1个结点)
        //并让p.next=null,从而让原第n-k个结点和第n-k+1个结点脱链。
        p=head;
        for(int i=0;i<len-k-1;i++){//让p指向链表第n-k个结点，
            p=p.next;
        }
        tail.next=head; //tail指向head
        head=p.next;//p的下一个结点是新的头结点
        p.next=null;//p充当新的尾部结点
        return head;
    }
    public void print(ListNode head){
        ListNode p=head;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LeetCode61 code = new LeetCode61();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        code.print(node1);//右移之前
        ListNode head=code.rotateRight(node1,2);
        code.print(head);//右移之后
    }
}

image-20231222170744430