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 个节点
思路一
采用快慢指
快指针与慢指针都以每步一个节点的速度向后遍历
快指针比慢指针先走 N 步
当快指针到达终点时，慢指针正好是倒数第 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;}思路二
获取单链表的倒数第 N + 1 与倒数第 N 个节点
将倒数第 N + 1 个节点的 next 指向 null
将链表尾节点的 next 指向 head
返回倒数第 N 个节点
例如链表 A -> B -> C -> D -> E 右移 2 位，依照上述步骤为：
获取节点 C 与 D
A -> B -> C -> null, D -> E
D -> E -> A -> B -> C -> nul
返回节点 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 tmpCPP 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)$
最后更新于
这有帮助吗？