LeetCode日记–61.Rotate List

发布于 2020-09-23  113 次阅读


碎碎念:今天公布了大二的分数成绩。。。我觉得保研没希望了。。要多刷刷LeetCode了。

题目如下:

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模链表长度n(这样如果k≥n就可以少变换n的倍数次,因为变了n次等于没有变)。但是我突然发现这里的链表不是双向链表,也就是说第一次把末尾的指针换到第一个位置以后,就会丢失掉指向队尾的指针。

官方题解思路:

其实在写代码的时候我发现其实在换头的时候,会把链表的首尾连在一起,那么我们为什么不直接先把链表连成一个环,然后利用数学推演可以知道新链表的头就是在头后面的n-k处,新的链尾则是在n-k-1处。

下一个问题是我们怎么知道n为多少呢?

因为我们需要把链表首尾相连,因此我们必须要遍历整个链表找到表尾。这时我们顺便计数,就可以知道n的值了。

思路已经很清晰了,让我们看看代码:

官方实现:

class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // base cases
    if (head == null) return null;
    if (head.next == null) return head;

    // close the linked list into the ring
    ListNode old_tail = head;
    int n;
    for(n = 1; old_tail.next != null; n++)
      old_tail = old_tail.next;
    old_tail.next = head;

    // find new tail : (n - k % n - 1)th node
    // and new head : (n - k % n)th node
    ListNode new_tail = head;
    for (int i = 0; i < n - k % n - 1; i++)
      new_tail = new_tail.next;
    ListNode new_head = new_tail.next;

    // break the ring
    new_tail.next = null;

    return new_head;
  }
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/rotate-list/solution/xuan-zhuan-lian-biao-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我自己的实现:

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode cur = head;
        int count = 1;
        if(head == null)
            return null;
        while(cur.next!=null){
            cur = cur.next;
            count++;
        }
        cur.next = head;
        int moveTimes = count- (k%count);
        for(int i = 0;i<moveTimes;i++){
            head = head.next;
            // 此时cur作为尾指针
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
}

我的题解比官方题解复杂了一丢丢,就是在最终找新的指针的头尾的时候,我是一次移动头指针和尾指针,但是事实上只需要移动尾指针就可以了,尾指针的next就是新的头。不过这么一点点的时间开销大概是算不上什么了。


你好哇!欢迎来到雷公马碎碎念的地方:)