leetcode:61.旋转链表

亦凉 2023-07-10 15:42 4阅读 0赞

### 题目描述： ###

给定一个链表，旋转链表，将链表每个节点向右移动 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
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/rotate-list
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

###### 示例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的元素，在此时截断链表，分为两部分，然后把后半部分拿到前面即可。  
代码如下：

###### java： ######

/** * 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) { 
        	// 如果链表为空，或者旋转次数为0时，可以直接返回原链表
            if (head == null || k == 0) { 
                return head;
            }
            // 定义一个指向链表开头的指针
            ListNode current = head;
            // 最后返回结果的指针
            ListNode res = new ListNode(0);
            // 用来指向结果的指针
            ListNode p = res;
            // 链表的长度
            int length = 0;
    		// 计算链表的长度
            while (current != null) { 
                length++;
                current = current.next;
            }
            // 这里很容易知道：转了一圈又回到原点等于没动，所以取模简化
            if (k % length == 0) { 
                return head;
            }
            // 计算完长度，指针回到头节点
            current = head;
            // 用来存储指针移动后最后所处的位置，也就是需要head链表的前几个元素
            int falg = 0;
            // 这里要注意了，我刚开始以为旋转的意思就是指针向后移动几次而已
            //实际上是要把尾部的元素放到开头才对，这样就会有个差值，也就是计算长度的目的
            // 只需要对length取模即可。然后找到current应该处在的位置，就是该在什么地方切断
            for (int i = 0; i < length - k % length; i++) { 
                if (current != null) { 
                    current = current.next;
                    falg++;
                }
            }
            // 从标记位往后，添加到新链表中
            while (current != null) { 
                p.next = new ListNode(current.val);
                p = p.next;
                current = current.next;
            }
            // 最后把标记位之前到所有元素放到res最后面即可
            current = head;
            for (int i = 0; i < falg; i++) { 
                p.next = new ListNode(current.val);
                p = p.next;
                current = current.next;
            }
            return res.next;
        }
    }

###### python： ######

# Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution:
        def rotateRight(self, head: ListNode, k: int) -> ListNode:
            if head == None or k == 0:
                return head
            current, res = head, ListNode(0)
            p, length, flag = res, 0, 0
            while current != None:
                length += 1
                current = current.next
            if k % length == 0:
                return head
            current = head
            for i in range(length - k % length):
                if current != None:
                    flag += 1
                    current = current.next
            while current != None:
                p.next = ListNode(current.val)
                p = p.next
                current = current.next
            current = head
            for i in range(flag):
                p.next = ListNode(current.val)
                p = p.next
                current = current.next
            return res.next

##### 总结： #####

属于链表中比较常规的一道题。可配合官方的动画来看，这样就比较好理解。只要理解了题目意思，也就很简单了。