Skip to content

Latest commit

 

History

History
275 lines (236 loc) · 5.39 KB

61.Rotate-List.md

File metadata and controls

275 lines (236 loc) · 5.39 KB

题目地址(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, 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

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)$$