Open azl397985856 opened 3 years ago
C++ Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr) {
return head;
}
int len = 0;
auto tmp = head;
while (tmp != nullptr) {
tmp = tmp->next;
++len;
}
k %= len;
auto slow = head, fast = head;
while (k--) {
fast = fast->next;
}
while (fast->next != nullptr) {
slow = slow->next;
fast = fast->next;
}
fast->next = head;
auto res = slow->next;
slow->next = nullptr;
return res;
}
};
令 n 为链表长度。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
int len = getLen(head);
k = k % len;
if (k == 0) return head;
ListNode dummy = new ListNode(0, head), slow = dummy, fast = dummy;
while (k > 0){
fast = fast.next;
k--;
}
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
ListNode nextPart = slow.next;
slow.next = null;
fast.next = dummy.next;
dummy.next = nextPart;
return dummy.next;
}
private int getLen(ListNode head){
ListNode curt = head;
int len = 0;
while (curt != null){
len++;
curt = curt.next;
}
return len;
}
}
Time Complexity: O(n) Space Complexity: O(1)
C++思考方式: 将head指针复制为tail (这里tail是当前结点cur, 每次移动一位, 当tail的next为 NULL时, tail成为尾结点),先遍历一次算出长度len。
由于k可能会超过链表长度len,于是需要用一个预处理小技巧 - k对len取模,shift = k % len。如果shift = 0, 不需要继续处理了。
否则,将head指针复制为prev, 再while循环一次, 迭代次数为 len - shift。循环结束时, prev的next指针指向的位置就是所求链表的头结点。使用一个新的指针nextP占住prev的next指针指向的位置, 将head结点挂接到tail的next指针上,然后将prev的next置为NULL, 最后返回 nextP 指针。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL) return head;
int len = 1;
ListNode* tail = head;
/* while循环一次,得到长度len。这里tail是当前结点cur, 当tail的next为 NULL时, tail成为尾结点 */
while (tail->next)
{
tail = tail->next;
++len;
}
int shift = k % len;
if (shift == 0)
return head;
ListNode* prev = head;
/* 再while循环一次, 迭代次数为 len - shift */
while (--len > shift) // 处理len - shift个结点
{
prev = prev->next;
}
ListNode* nextP = prev->next;
tail->next = head;
prev->next = NULL;
return nextP;
}
};
代码已上传到: leetcode-ac/91algo daily - github.com
第一步,计算链表长度,k与长度的模。这里有两种特殊情况,一是模为零,则直接返回head,另一种是长度为0,返回None。 第二步,根据模,确定三个点,start(旋转后的head),pre(原链表start的前一个节点),point(原链表最后结点) 第三步,pre的next设为None(防止成环),point的next设为head,return start即可
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
c=0
t=head
while t!=None:
c+=1
t=t.next
if c==0:
return None
idx=k%c
if idx==0:
return head
pre=None
start=head
j=0
while j<c-idx:
pre=start
start=start.next
j+=1
pre.next=None
res=start
cnt=0
point=start
while point.next!=None:
point=point.next
point.next=head
return res
时间复杂度 :O(n)
空间复杂度:O(1)
Node1 -> Node2 -> Node 3 -> Node 4 -> Node 5 k=2 head prePointer pointer tail what I do is rebuilding the connection: prePointer.next = None; tail.next = head; return pointer
class Solution(object):
def rotateRight(self, head, k):
# edge case
if head == None:
return head
# get the length of the list
length = 1
cur = head
while cur.next:
length += 1
cur = cur.next
k = k%length
# edge cases
if k == 0:
return head
if head.next == None:
return head
# get the prePointer, pointer, tail
prePointer = head
rest = length-1
while rest > k:
prePointer = prePointer.next
rest -= 1
pointer = cur.next
prePointer.next = None
tail = pointer
while tail.next:
tail = tail.next
# rebuild the link
tail.next = head
return pointer
时间复杂度:O(n) 语言:c++; 代码实现: class Solution { public: ListNode rotateRight(ListNode head, int k) { //先找链表末尾,闭合成环,并计算长度 if(!head)return head; ListNodecur=head; int count=1; while(cur->next) { count++; cur=cur->next; } cur->next=head; k=k%count; //找倒数第k个结点,让其成为头结点,并断开原本顺序倒数k+1到倒数k结点的连接 cur=head; int j=1; while(j<count-k) { cur=cur->next; j++; } ListNodenewhead=cur->next; cur->next=NULL; return newhead; } };
更新head和指向NULL的结点
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
//base case
if (head == NULL) return NULL;
//若链表结点数为n,即无非就是取第n-k个结点
//将该结点的下一个结点变为head,该结点的next指向NULL;
int n = 1;
ListNode* cur = head;
while (cur->next) {
n ++;
cur = cur->next;
}
//闭合成环(要考虑到k > n的情况)
cur->next = head;
int num = n - (k % n) - 1;
cur = head;
while (num --) cur = cur->next;
ListNode* res = cur->next;
cur->next = NULL;
return res;
}
};
时间复杂度:O(n)链表结点一共n个,最后位置在第i个,那么为O(n + i),即为O(n) 空间复杂度:O(1) 原地操作
length == 0
, return head
.k >= n
, then we can do k = k % n
which doesn't affect the final result but reduce the number of rotations.Modify the linked list. The last kth element will be the new head, and its previous node's next will be null
, and the last node will point the the original head.
class Solution {
public ListNode rotateRight(ListNode head, int k) {
int n = getLength(head);
if (n == 0) return head;
k %= n;
// Find the last kth element as new head
ListNode fast = head, slow = head;
for (int i = 0; i < k; ++i) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
fast.next = head;
ListNode newHead = slow.next;
slow.next = null;
return newHead;
}
private int getLength(ListNode head) {
int len = 0;
while (head != null) {
++len;
head = head.next;
}
return len;
}
}
Time: O(n)
Space: O(1)
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
length = 0
current = head
while(current != None):
length += 1
current = current.next
if length == 0:
return None
if k % length == 0:
return head
needStep = length - k % length - 1
current = head
for _ in range(needStep):
current = current.next
newTail = current
current = current.next
newHead = current
while(current.next != None):
current = current.next
newTail.next = None
current.next = head
return newHead
时间复杂度 :O(n)
空间复杂度:O(1)
https://leetcode.com/problems/rotate-list/
Medium
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# border check
if head == None:
return head
# find the length of the linked list
t, length = head, 1
while t.next != None:
t = t.next
length += 1
# get the actual rotate steps
k = k % length
# find the kth node from tail
tail = head
for _ in range(k):
tail = tail.next
prev = head
while tail.next != None:
prev = prev.next
tail = tail.next
# link the list again
tail.next = head
head = prev.next
prev.next = None
return head
时间复杂度:O(n) 空间复杂度:O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k == 0:
return head
length = 0
cur = head
while cur:
length += 1
cur = cur.next
if length in (0, 1):
return head
fast = head
slow = head
for _ in range(k % length):
fast = fast.next
while fast.next and slow:
fast = fast.next
slow = slow.next
fast.next = head
cur = slow.next
slow.next = None
return cur
python
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return head
i = 0
count = 1
fast = slow = head
while i < k:
if fast.next:
fast = fast.next
count += 1
else:
fast = head
k = k % count
i = -1
i += 1
while fast.next:
fast = fast.next
slow = slow.next
if slow.next:
new_head = slow.next
slow.next = None
fast.next = head
head = new_head
return head
https://leetcode-cn.com/problems/rotate-list/
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109
Java Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null){
return null;
}
ListNode slow = head;
int count = 1;
while (slow.next != null){
count ++;
slow = slow.next;
}
// 尾结点
ListNode tail = slow;
k = k % count;
if(k == 0){
return head;
}
slow = head;
ListNode fast = head;
for(int i=0;i<k;i++){
fast = fast.next;
}
while (fast.next != null){
slow = slow.next;
fast = fast.next;
}
ListNode newHead = slow.next;
tail.next = head;
slow.next = null;
return newHead;
}
}
复杂度分析
令 n 为数组长度。
用快慢指针,分别指到最后一个和倒数第k个。此时,慢指针的next即为head,将慢指针next指成null, 快指针指到head。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (!head || !head.next) return head;
let length = 0
let cur = head
while(cur) {
cur = cur.next
length++
}
k = k % length
if (!k) {
return head
}
let fast = head
let slow = head
while(k > 0) {
fast = fast.next
k--
}
while(fast.next) {
fast = fast.next
slow = slow.next
}
let res = slow.next
slow.next = null
fast.next = head;
return res
};
时间复杂度 O(n) 空间复杂度 O(1)
ListNode* rotateRight(ListNode* head, int k)
{
if (k == 0)
return head;
ListNode *p = head;
int len = 0;
while(p->next)
{
len++;
p = p->next;
}
len++;
k = k % len;
p->next = head;
p = head;
int flag = 0;
// 找到尾节点
while(flag != (len - k - 1))
{
p = p->next;
flag++;
}
// 赋值头节点
ListNode *q = p->next;
//赋值尾节点
p->next = nullptr;
return q;
}
无论是什么方法,都得先判断链表的长度,减少不必要的链表旋转。确定好实际需要旋转次数后,有两种思路进行实际的旋转
暴力法
class Solution(object):
def rotateRight(self, head, k):
if head == None or head.next == None:
return head
l = 1
current = head
while current.next:
current = current.next
l += 1
k = k%l
def rotate(h):
prev = h
cur = h.next
while cur.next:
prev = prev.next
cur = cur.next
cur.next = h
prev.next = None
return cur
while k > 0:
head = rotate(head)
k -= 1
return head
快慢指针
class Solution(object):
def rotateRight(self, head, k):
if head == None or head.next == None:
return head
l = 1
current = head
while current.next:
current = current.next
l += 1
k = k%l
if k == 0: return head
slow, fast = head, head
while k > 0:
fast = fast.next
k -= 1
while fast.next:
slow = slow.next
fast = fast.next
fast.next = head
head = slow.next
slow.next = None
return head
先首尾相连,然后找准位置断开。
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head == null || k == 0) return head;
var num = 1
var node = head
while (node?.next != null) {
num++
node = node.next
}
node?.next = head
var offset = num - (k % num)
if (offset == 0) return head
node = head
while (--offset > 0) {
node = node?.next
}
val res = node?.next
node?.next = null
return res
}
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k <= 0) return head;
int total = 1;
ListNode cur = head;
while (cur != null && cur.next != null) {
total++;
cur = cur.next;
}
cur.next = head;
k = total - (k % total);
if (k == 0) return head;
while (--k > 0) {
head = head.next;
}
ListNode res = head.next;
head.next = null;
return res;
}
}
O(len(list))
注意影响bug free的因素: 边界问题。k可长可短,如果为0怎么办;如果超过length怎么办,如果超过length但是回头了(%length == 0)怎么办?
k % length = 0
,这个一定要return
,否则会有错误答案。AC
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null || k == 0) return head;
int length = 0;
ListNode cur = head;
while(cur.next != null){
cur = cur.next;
length++;
}
length++;
ListNode old_tail = cur;
if(k % length == 0) return head;
cur = head;
int count = length - k % length;
while(--count > 0){
cur = cur.next;
}
ListNode new_head = cur.next;
cur.next = null;
old_tail.next = head;
return new_head;
}
}
time: O(N) space: O(1)
https://leetcode.com/problems/rotate-list/
const rotateRight = function (head, k) {
//find the length
let length = 1;
let pt = head;
while (pt && pt.next) {
length++;
pt = pt.next;
}
//we're using modulo for the edge case of if the length is smaller than k
k = k % length;
//edge case -> if k is 0, we don't need a rotation
if (k === 0) {
return head;
}
//find the new tail
let newTail = head;
let spaces = length - k;
while (spaces > 1) {
spaces--;
newTail = newTail.next;
}
//save the new head and reset appropriately
let newHead = newTail.next;
newTail.next = null;
pt.next = head;
return newHead;
};
时间 O(n) 空间 O(1)
这道题很直观,先算出总长度count,再使用快慢指针找到倒数的第k%count的数字,本质上rotate就是让这个数字变成head并链接上之前的list。有一些edge case 需要考虑
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# rotating by k means to take the kth (reversed) element and links its to the beginnng
count = 0
cur = head
while cur:
cur = cur.next
count+=1
if count:
k = k%count
if k == 0 or not head:
return head
fast = slow = head
prev = None
while k > 1:
fast = fast.next
k-=1
while fast and fast.next and slow and slow.next:
fast = fast.next
prev = slow
slow = slow.next
if prev:
prev.next = None
fast.next = head
return slow
Time: O(n) Space: O(1)
Language: Java
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Find length of list, and get the min k
int count = 0;
ListNode cur = head;
while (cur != null) {
cur = cur.next;
count++;
}
k = k % count;
if (k == 0) {
return head;
}
ListNode slow = head;
ListNode fast = head;
count = 0;
while (count < k) {
fast = fast.next;
count++;
}
// Find the new head
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// slow.next is the new head
ListNode newHead = slow.next;
fast.next = head;
slow.next = null;
return newHead;
}
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return head
length = 1
tail = head
while tail.next:
tail = tail.next
length += 1
k = k % length
if k == 0:
return head
cur = head
for i in range(length-k-1):
cur = cur.next
ans = cur.next
cur.next = None
tail.next = head
return ans
time: O(n) space: O(1)
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) return null;
int n = 0;
ListNode dummy = new ListNode(-200, head);
ListNode tail = dummy.next;
while (tail != null && tail.next != null) {
n ++;
tail = tail.next;
}
n ++;
if (n == k) return head;
int pos = k > n ? n - k % n : n - k;
ListNode cur = dummy;
for (int i = 0; i < pos; i ++) {
cur = cur.next;
}
tail.next = dummy.next;
dummy.next = cur.next;
cur.next = null;
return dummy.next;
}
}
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next or k==0:
return head
#find the length
length=0
cur = head
while cur:
length+=1
cur=cur.next
k=k%length
if k==0:
return head
#fast and slow pointers
fast=head
slow=head
while k>0:
fast=fast.next
k-=1
while fast and fast.next:
fast = fast.next
slow = slow.next
newHead = slow.next
fast.next=head
slow.next=None
return newHead
时间复杂度: O(N) 空间复杂度: O(1)
K can be larger than length so we need to know length and use k = k % len to find effective rotations. Then we can find the K+1 node from the tail, which is the (len - k) node from the head. This node will be the new tail, and node.next will be the new head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head: return head
tail = head
l = 1
while tail.next:
tail = tail.next
l += 1
k = k % l
if k == 0: return head
# Get the k+1 node from the tail
p = head
for _ in range(l - k - 1):
p = p.next
# p will be the new tail and p.next is the new head
tail.next = head
head = p.next
p.next = None
return head
Time complexity: O(N)
Space complexity: O(1)
思路要点:
‘def rotateRight(self, head, k):
if not head:
return None
if head.next == None:
return head
pointer = head
length = 1
while pointer.next:
pointer = pointer.next
length += 1
rotateTimes = k%length
if k == 0 or rotateTimes == 0:
return head
fastPointer = head
slowPointer = head
for a in range (rotateTimes):
fastPointer = fastPointer.next
while fastPointer.next:
slowPointer = slowPointer.next
fastPointer = fastPointer.next
temp = slowPointer.next
slowPointer.next = None
fastPointer.next = head
head = temp
return head’
思路:
将list向右旋转k步即为将list的头(head)向右移动 n - k步, 也就是新的头结点是第n - k个结点
复杂度分析:
代码(C++):
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
int n = 1;
ListNode* p = head;
// get the length of list
while (p->next) {
p = p->next;
++n;
}
// connect to a cycled list
p->next = head;
int left = n - k % n;
while (left--)
p = p->next;
head = p->next;
// break the cycle
p->next = nullptr;
return head;
}
};
Two pointers. Similar to the 'find the kth node from backward problem'.
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head: return None
p1, p2 = head, head
N = 0
while p2:
p2 = p2.next
N += 1
k %= N
if k == 0: return head
p2 = head
while k > 0:
p2 = p2.next
k -= 1
while p2.next:
p2 = p2.next
p1 = p1.next
newhead = p1.next
p1.next = None
p2.next = head
return newhead
class Solution {
public ListNode rotateRight(ListNode head, int k) {
Queue<ListNode> queue = new LinkedList();
int length = 0;
ListNode current = head;
while (current != null) {
queue.add(current);
current = current.next;
length++;
}
int moveSteps = length - k % length;
for (int i=0; i<moveSteps; i++) {
queue.add(queue.poll());
}
ListNode newHead = queue.poll();
ListNode pre = newHead;
while (!queue.isEmpty()) {
current = queue.poll();
pre.next = current;
pre = current;
}
pre.next = null;
return newHead;
}
}
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
//get length of list
int length = 0;
ListNode current = head;
while (current != null) {
current = current.next;
length++;
}
k = k % length;
if (k == 0) {
return head;
}
ListNode fast = head;
ListNode slow = head;
//fast move ksteps, then slow move
for (int i=0; i<k; i++) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode newTail = slow;
ListNode tail = fast;
ListNode newHead = newTail.next;
newTail.next = null;
tail.next = head;
return newHead;
}
Explanation
l
and its last element oldTail
.(l - k % l - 1)th
node.(l - k % l)th
node.Python
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# base case
if not head or not head.next:
return head
oldTail = head
l = 1
while oldTail.next:
oldTail = oldTail.next
l += 1
oldTail.next = head
# new tail: l - k % l - 1
# new head: l - k % l
newTail = head
for i in range(l - k % l - 1):
newTail = newTail.next
newHead = newTail.next
newTail.next = None
return newHead
Complexity
O(N)
O(1)
先遍历一遍链表,求得链表长度 ln
, 如果 k > ln
, 则k = k % ln
将k
的范围转换到0 ~ ln - 1
。原链表的尾节点为taill
。
求得新链表的尾节点ptail
(原链表第ln - k
个节点), 头节点phead
(ptail
在原链表的下一个节点)。
然后ptail -> next = NULL; taill -> next = head
。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == nullptr || k == 0) return head;
int ln = 0;
ListNode *ptmp, *pt;
ptmp = head;
while(ptmp){
++ ln;
pt = ptmp;
ptmp = ptmp -> next;
}
k = k % ln;
if(k == 0) return head;
ListNode *ph;
ptmp = head;
for(int ii = 0; ii < ln - k - 1; ++ ii){
ptmp = ptmp -> next;
}
pt -> next = head;
head = ptmp -> next;
ptmp -> next = nullptr;
return head;
}
};
复杂度分析
O(n)
O(1)
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head: return None
#check the length
lastNode, length = head, 1
while lastNode.next:
lastNode = lastNode.next
length += 1
# check the number of rotation
k = k % length
# setlast node point to the first node
lastNode.next = head
#traverse until (length - k) node
temp = head
for i in range(length - k - 1):
temp = temp.next
#disconnect the first and last node
out = temp.next
temp.next = None
return out
Time: $O(n)$
Space: $O(1)$
让链表首位连接成环,再在相应位置断开即得所求。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0){
return head;
}
int n = 1;
ListNode newHead = head;
while (newHead.next != null){
n++;
newHead = newHead.next;
}
int add = n - (k % n);
if (add % n == 0) {
return head;
}
newHead.next = head;
while (add-- > 0){
newHead = newHead.next;
}
ListNode tmp = newHead.next;
newHead.next = null;
return tmp;
}
}
idea: recursion. rotate the linkedlist by k-1 times plus one more time. Time: O(n^2) Space: O(n)
/**
}
*/
class Solution {
int size=0;
public ListNode rotateRight(ListNode head, int k) {
if (head==null)
return head;
if(size==0) {
ListNode curr=head;
while(curr!=null) {
curr=curr.next;
size++;}
}
k=k%size;
if(k==0)
return head;
if(k==1) {
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null) {
slow=fast;
fast=fast.next;
}
slow.next=null;
fast.next=head;
return fast;
}
ListNode temp=rotateRight(head,k-1);
return rotateRight(temp,1);
} }
https://leetcode-cn.com/problems/rotate-list/
将list的尾部连上头部,然后head指针移动len - k - 1步,head移动到新的listnode的前一个node,然后断开。需要注意的是k可能大于list的长度,所以需要len - k % len.
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode index = head;
int len = 1;
while(index.next != null) {
index = index.next;
len++;
}
index.next = head;
for(int i = 1; i < len - k % len; i++) {
head = head.next;
}
ListNode res = head.next;
head.next = null;
return res;
}
}
O(n)
O(1)
先求长度 n 和尾巴
然后k mod 长度
然后找到 新的head 分割 重新连接
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next:
return head
# get list length
list_length = 0
cur = head
tail = None
while cur:
list_length += 1
cur = cur.next
if cur:
tail = cur
# handle k = 0 case
k = k % list_length
if k == 0:
return head
count = 0
cur = head
while count < list_length - k - 1:
count += 1
cur = cur.next
new_head = cur.next
cur.next = None
tail.next = head
return new_head
time complexity O(n) space complexity O(1)
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return
nxt = head
lenth = 1
while head.next:
head = head.next
lenth += 1
head.next = nxt
k = k % lenth
cut = lenth - k - 1
for _ in range(cut):
nxt = nxt.next
ans, nxt.next = nxt.next, None
return ans
var rotateRight = function(head, k) {
let lens = 1;
let tail = head;
while(tail && tail.next){
lens++;
tail =tail.next;
}
//we're using modulo for the edge case of if the length is smaller than k
k = k% lens;
//edge case -> if k is 0, we don't need a rotation
if( k === 0){
return head;
}
let newTail = head;
//if space is not bigger than one we dont need to move the newTail
let space = lens-k;
//find the new tail
while(space > 1 ){
space --;
newTail = newTail.next;
}
//save the new head and reset appropriately
let newHead = newTail.next;
tail.next = head;
newTail.next = null;
return newHead;
};
//time O(n)
//space O(1)
思路并不难,改变指向时需要多多注意,以及小心边界情况。
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return head;
int n = 0;
ListNode cur = head;
// O(n)
ListNode last = null;
while (cur != null) {
n++;
if (cur.next == null)
last = cur;
cur = cur.next;
}
k = k % n;
if (k == 0)
return head;
k = n - k;
cur = head;
while (--k > 0) {
cur = cur.next;
}
ListNode ans = cur.next;
cur.next = null;
last.next = head;
return ans;
}
}
模拟
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next:
return head
length = 0
virtualhead = ListNode(-1,head)
cur = virtualhead
while cur.next:
length+=1
cur = cur.next
cur.next = head
k = k%length
cur = head
for i in range(length-k-1):
cur = cur.next
virtualhead.next=cur.next
cur.next=None
return virtualhead.next
通过双指针,先把整个链表形成一个循环,然后计算移动到k步之后的链头,断开循环,形成新的链表
Python3 Code:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head == None:
return head
headPoint = head
length = 1
while head.next != None:
head = head.next
length += 1
endPoint = head
endPoint.next = headPoint #形成一个循环
moveLength = length - (k % length) - 1 #得出移动步数
print(moveLength)
while moveLength != 0:
headPoint = headPoint.next
moveLength -= 1
endPoint = headPoint
headPoint = headPoint.next
endPoint.next = None
return headPoint
复杂度分析
令 n 为数组长度。
var rotateRight = function(head, k) {
var p = head;
var count = 0;
while (p !== null) {
count++;
p = p.next;
}
k = k % count;
var fast = head;
var slow = head;
for (var i = 0; i < k; i++) {
fast = fast.next;
}
if (fast === null) return head;
while (fast.next !== null) {
fast = fast.next;
slow = slow.next;
}
fast.next = head;
fast = slow.next;
slow.next = null;
return fast;
};
先计算链表长度,根据长度把k取余 观察题目发现新的头节点是原链表的倒数第k个节点 双指针方法求倒数第k+1个节点,同时可以得到尾节点。 最后修改相关节点next指针,返回结果。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (head === null || head.next === null) {
return head;
}
let len = 0;
let node = head;
while (node !== null) {
len++;
node = node.next;
}
k = k % len;
if (k === 0) {
return head;
}
let first = head;
let second = head;
while (first.next !== null) {
first = first.next;
if (k > 0) {
k--;
} else {
second = second.next;
}
}
let newHead = second.next;
second.next = null;
first.next = head;
return newHead;
};
复杂度分析
思路:先遍历链表得到表的长度length, 标记链表尾为tail, 记录k mod length 为 true_k,从表首前进length - true_k - 1 次 得到新链表的尾new_tail, 记录new_tail的下一个元素为new_head, 连接旧表尾和旧表首, 更新new_tail的next为None, 返回 new_head
Python 3 code :
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head == None or head.next == None:
return head
length = 1
pt = head
while pt.next != None:
pt = pt.next
length += 1
old_tail = pt
true_k = k % lenth
if true_k == 0: return head
num_to_move = length - true_k
cur = head
while num_to_move - 1:
cur = cur.next
num_to_move -= 1
new_tail = cur
new_head = cur.next
old_tail.next = head
new_tail.next = None
return new_head
Time Complexity: O(n) as we scan through the linked list to get length. Space Complexity: O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
ListNode iter = head;
int len = 1;
while(iter.next != null){
iter = iter.next;
len++;
}
int add = len - k % len;
iter.next = head;
if (add == len) {
return head;
}
while(add-- > 0){
iter = iter.next;
}
ListNode resHead = iter.next;
iter.next = null;
return resHead;
}
private int getLength(ListNode head){
int n = 1;
while(head.next != null){
head = head.next;
n++;
}
return n;
}
}
— 时间复杂度:O(n)
— 空间复杂度:O(1)
思路: 1.自己有思路,但是没写出来,然后对了答案。 于是: 【记得考虑边界条件,如k=0, 链表为空,链表为1】 首先遍历链表获得链长n,关键是n初始值为1 且判断链表下一位不为空 即 pre.Next != nil 然后首尾相接组成环 倒数M位 = 整数N位 - k%N = add【步数】 然后再for add > 0 判断,获得倒数第一位置。然后输出为pre.Next ,再把pre.Next = nil 打断即可
func rotateRight(head *ListNode, k int) *ListNode {
if k == 0 || head == nil || head.Next == nil {
return head
}
pre := head
n := 1
for pre.Next != nil{
pre = pre.Next
n++
}
add := n - k%n
if add == n{
return head
}
pre.Next = head
for add > 0{
pre = pre.Next
add--
}
next := pre.Next
pre.Next = nil
return next
}
补充一种快慢指针做法
func rotateRight(head *ListNode, k int) *ListNode {
if k == 0 || head == nil || head.Next == nil {
return head
}
num := 1
cur := head
for cur.Next != nil{
cur = cur.Next
num++
}
slow, fast := head, head
k %= num
for k > 0{
fast = fast.Next
k--
}
for fast.Next != nil{
slow = slow.Next
fast = fast.Next
}
fast.Next = head
out := slow.Next
slow.Next = nil
return out
}
— 时间复杂度:O(n)
— 空间复杂度:O(1)
快慢指针
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head||!head->next||k==0)
return head;
ListNode* fast=head,*slow=head;
int total=1;
while(fast->next)
{
fast=fast->next;
total++;
}
k%=total;
fast=head;
for(int i=0;i<k;i++)
fast=fast->next;
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
fast->next=head;
fast=slow->next;
slow->next=nullptr;
return fast;
}
};
复杂度分析
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(k == 0 || head == null) return head;
//获取链表长度
int length = 0;
for (ListNode current = head; current != null; current = current.next)
length++;
//用长度对k求余数获取从某个节点开始旋转
int index = length - k % length;
ListNode current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
if(current.next == null) return head;
ListNode tempHead = current.next;
current.next = null;
ListNode node = tempHead;
for(; node.next != null; node = node.next);
node.next = head;
return tempHead;
}
}
时间复杂度: 总时间复杂度为O(2*n)。所以时间复杂度为O(n) n为链表长度 空间复杂度: O(1)
Algo
- get the nodes -k and -k-1: by quick/slow pointer
- set node_(-k-1).next to none
- combine tail.next and head
- return node -k
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# corner cases
if not head or not head.next: return head
# save a len for super big k
list_len = 0
count = 0
# slow/quick
quick, slow = head, head
while count < k:
# k can be more than len(linkedlist)
if not quick.next:
list_len += 1
k = k % list_len
quick = head
count = 0
continue
quick = quick.next
list_len += 1
count += 1
while quick.next:
slow = slow.next
quick = quick.next
# check if it's a full circle
if not slow.next: return head
# now slow is the last node
new_head = slow.next
slow.next = None
quick.next = head
return new_head
先求链表长度len,k=k%len,之后将倒数第k个节点作为新的链表头,断开倒数第k+1与倒数第k个节点。
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next: return head
p = head
l = 1
while p.next:
p = p.next
l += 1
p.next = head
k = k % l
q = head
for i in range(l - k - 1):
q = q.next
head = q.next
q.next = None
return head
复杂度
61. 旋转链表
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/rotate-list/
前置知识
题目描述
示例 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