[刷题防痴呆] 0061 - 旋转链表 (Rotate List

题目地址

https://leetcode.com/problems/rotate-list/description/

题目描述

61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

 

Example 1:


Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:


Input: head = [0,1,2], k = 4
Output: [2,0,1]

思路

• 先计算linkedlist总共多长.
• k = k % length.
• 快慢指针. 快指针先走k步.
• 然后快慢指针一起走. 当快指针走到尾部时, 进行交换.
• fast.next = dummy.next. res = slow.next. slow.next = null.
• 最后返回res.

关键点

代码

• 语言支持：Java

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        int length = getLength(head);
        k = k % length;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return fast;
            }
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        fast.next = dummy.next;
        ListNode res = slow.next;
        slow.next = null;
        return res;
    }

    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}