Leetcode刷题java之61. 旋转链表(一天一道编程题之第三天)

本是古典何须时尚 2023-07-07 11:25 15阅读 0赞

执行结果：

通过

显示详情

执行用时 :2387 ms, 在所有 Java 提交中击败了5.24% 的用户

内存消耗 :38.2 MB, 在所有 Java 提交中击败了5.06%的用户

题目：

给定一个链表，旋转链表，将链表每个节点向右移动 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/rotate-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

找到倒数第k个节点，然后调整指针的顺序，利用快慢指针找到节点。

代码：

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(head==null)
            {
                return head;
            }
            ListNode slow=head;
            ListNode fast=head;
            while(k-->0)
            {
                fast=fast.next==null?head:fast.next;
            }
            //此时s如果slow和fast是同一个节点的话，就直接输出就可以了
            if(slow==fast)
            {
                return head;
            }
            while(fast.next!=null)
            {
                slow=slow.next;
                fast=fast.next;
            }
            ListNode result=slow.next;
            slow.next=null;
            fast.next=head;
            return result;
        }
    }