美文网首页
LeetCode实战:旋转链表

LeetCode实战:旋转链表

作者: 老马的程序人生 | 来源:发表于2019-04-22 09:40 被阅读0次

    题目英文

    Given a linked list, rotate the list to the right by k places, where k is non-negative.

    Example 1:

    Input: 1->2->3->4->5->NULL, k = 2

    Output: 4->5->1->2->3->NULL

    Explanation:

    rotate 1 steps to the right: 5->1->2->3->4->NULL

    rotate 2 steps to the right: 4->5->1->2->3->NULL

    Example 2:

    Input: 0->1->2->NULL, k = 4

    Output: 2->0->1->NULL

    Explanation:

    rotate 1 steps to the right: 2->0->1->NULL

    rotate 2 steps to the right: 1->2->0->NULL

    rotate 3 steps to the right: 0->1->2->NULL

    rotate 4 steps to the right: 2->0->1->NULL


    题目中文

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


    算法实现

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
     
    public class Solution
    {
        public ListNode RotateRight(ListNode head, int k)
        {
            if (head == null || k == 0)
                return head;
    
            int len = GetLength(head);
            int index = len - k%len;
    
            if (index == len)
                return head;
    
            ListNode temp1 = head;
            ListNode temp2 = head;
            for (int i = 0; i < index - 1; i++)
            {
                temp1 = temp1.next;
            }
            head = temp1.next;
            temp1.next = null;
    
            temp1 = head;
            while (temp1.next != null)
            {
                temp1 = temp1.next;
            }
            temp1.next = temp2;
            return head;
        }
    
        public int GetLength(ListNode head)
        {
            ListNode temp = head;
            int i = 0;
            while (temp != null)
            {
                i++;
                temp = temp.next;
            }
            return i;
        }
    } 
    

    实验结果

    旋转链表

    相关图文

    相关文章

      网友评论

          本文标题:LeetCode实战:旋转链表

          本文链接:https://www.haomeiwen.com/subject/icvegqtx.html