LeetCode_双指针_中等_61.旋转链表

清疚 2023-10-06 23:16 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。**

**示例 1：**

![在这里插入图片描述][320bf3cd1c964bb39473be406b319932.png]

输入：head = \[1,2,3,4,5\], k = 2  
输出：\[4,5,1,2,3\]

**示例 2：**

![在这里插入图片描述][bc0e875961d04e65be55beebe8fab9d4.png]

输入：head = \[0,1,2\], k = 4  
输出：\[2,0,1\]

**提示：**  
链表中节点的数目在范围 \[0, 500\] 内  
\-100 <= Node.val <= 100  
0 <= k <= 2 \* 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/rotate-list

## 2.思路 ##

（1）双指针  
详细分析过程见下面代码中的注释。

## 3.代码实现（Java） ##

//思路1————双指针
    /**
     * 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 (k == 0 || head == null || head.next == null) {
        
                return head;
            }
            int n = 1;
            ListNode iter = head;
            while (iter.next != null) {
        
                iter = iter.next;
                n++;
            }
            int add = n - k % n;
            if (add == n) {
        
                return head;
            }
            iter.next = head;
            while (add-- > 0) {
        
                iter = iter.next;
            }
            ListNode ret = iter.next;
            iter.next = null;
            return ret;
        }
    }

[320bf3cd1c964bb39473be406b319932.png]: https://img-blog.csdnimg.cn/320bf3cd1c964bb39473be406b319932.png
[bc0e875961d04e65be55beebe8fab9d4.png]: https://img-blog.csdnimg.cn/bc0e875961d04e65be55beebe8fab9d4.png