0061. 旋转链表

题目地址(61. 旋转链表)

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

题目描述

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

快慢指针法

前置知识

• 求单链表的倒数第 N 个节点

思路一

1. 采用快慢指

2. 快指针与慢指针都以每步一个节点的速度向后遍历

3. 快指针比慢指针先走 N 步

4. 当快指针到达终点时，慢指针正好是倒数第 N 个节点

思路一代码

• 伪代码

快指针 = head;
慢指针 = head;
while (快指针.next) {
  if (N-- <= 0) {
    慢指针 = 慢指针.next;
  }
  快指针 = 快指针.next;
}

• 语言支持: JS

JS Code:

let slow = (fast = head);
while (fast.next) {
  if (k-- <= 0) {
    slow = slow.next;
  }
  fast = fast.next;
}

思路二

1. 获取单链表的倒数第 N + 1 与倒数第 N 个节点

2. 将倒数第 N + 1 个节点的 next 指向 null

3. 将链表尾节点的 next 指向 head

4. 返回倒数第 N 个节点

例如链表 A -> B -> C -> D -> E 右移 2 位，依照上述步骤为：

1. 获取节点 C 与 D

2. A -> B -> C -> null, D -> E

3. D -> E -> A -> B -> C -> nul

4. 返回节点 D

注意：假如链表节点长度为 len， 则右移 K 位与右移动 k % len 的效果是一样的 就像是长度为 1000 米的环形跑道， 你跑 1100 米与跑 100 米到达的是同一个地点

思路二代码

• 伪代码

  获取链表的长度
  k = k % 链表的长度
  获取倒数第k + 1,倒数第K个节点与链表尾节点
  倒数第k + 1个节点.next = null
  链表尾节点.next = head
  return 倒数第k个节点

• 语言支持: JS, JAVA, Python, CPP, Go, PHP

JS Code:

var rotateRight = function (head, k) {
  if (!head || !head.next) return head;
  let count = 0,
    now = head;
  while (now) {
    now = now.next;
    count++;
  }
  k = k % count;
  let slow = (fast = head);
  while (fast.next) {
    if (k-- <= 0) {
      slow = slow.next;
    }
    fast = fast.next;
  }
  fast.next = head;
  let res = slow.next;
  slow.next = null;
  return res;
};

JAVA Code:

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;
        int count = 0;
        ListNode now = head;
        while(now != null){
            now = now.next;
            count++;
        }
        k = k % count;
        ListNode slow = head, fast = head;
        while(fast.next != null){
            if(k-- <= 0){
                slow = slow.next;
            }
            fast = fast.next;
        }
        fast.next = head;
        ListNode res = slow.next;
        slow.next = null;
        return res;
    }
}

Python Code:

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # 双指针
        if head:
            p1 = head
            p2 = head
            count = 1
            i = 0
            while i < k:
                if p2.next:
                    count += 1
                    p2 = p2.next
                else:
                    k = k % count
                    i = -1
                    p2 = head
                i += 1

            while p2.next:
                p1 = p1.next
                p2 = p2.next

            if p1.next:
                tmp = p1.next
            else:
                return head
            p1.next = None
            p2.next = head
            return tmp

CPP Code:

class Solution {
    int getLength(ListNode *head) {
        int len = 0;
        for (; head; head = head->next, ++len);
        return len;
    }
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return NULL;
        int len = getLength(head);
        k %= len;
        if (k == 0) return head;
        auto p = head, q = head;
        while (k--) q = q->next;
        while (q->next) {
            p = p->next;
            q = q->next;
        }
        auto h = p->next;
        q->next = head;
        p->next = NULL;
        return h;
    }
};

Go Code:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    n := 0
    p := head
    for p != nil {
        n++
        p = p.Next
    }
    k = k % n
    // p 为快指针, q 为慢指针
    p = head
    q := head
    for p.Next!=nil {
        p = p.Next
        if k>0 {
            k--
        } else {
            q = q.Next
        }
    }
    // 更新指针
    p.Next = head
    head = q.Next
    q.Next = nil

    return head
}

PHP Code:

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function rotateRight($head, $k)
    {
        if (!$head || !$head->next) return $head;

        $p = $head;
        $n = 0;
        while ($p) {
            $n++;
            $p = $p->next;
        }
        $k = $k % $n;
        $p = $q = $head; // $p 快指针; $q 慢指针
        while ($p->next) {
            $p = $p->next;
            if ($k > 0) $k--;
            else $q = $q->next;
        }
        $p->next = $head;
        $head = $q->next;
        $q->next = null;

        return $head;
    }
}

复杂度分析

• 时间复杂度：节点最多只遍历两遍，时间复杂度为$O(N)$

• 空间复杂度：未使用额外的空间，空间复杂度$O(1)$