A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
2 Add Two Numbers
21 Merge Two Sorted Lists
23 Merge k Sorted Lists
61 Rotate List
82 Remove Duplicates from Sorted List II
83 Remove Duplicates from Sorted List
86 Partition List
92 Reverse Linked List II
109 Convert Sorted List to Binary Search Tree
141 Linked List Cycle
142 Linked List Cycle II
203 Remove Linked List Elements
206 Reverse Linked List
234 Palindrome Linked List
237 Delete Node in a Linked List
328 Odd Even Linked List
369 Plus One Linked List
379 Design Phone Directory
445 Add Two Numbers II
725 Split Linked List in Parts
817 Linked List Components
148 Sort List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By GitBook
61 Rotate List

1. Question

Given a list, rotate the list to the right bykplaces, wherekis non-negative.
Example:
1
Given 1->2->3->4->5->NULL and k= 2,
2
​
3
return 4->5->1->2->3->NULL.
Copied!

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode rotateRight(ListNode head, int k) {
11
if (head == null || k == 0) {
12
return head;
13
}
14
​
15
int len = 1;
16
ListNode curNode = head;
17
​
18
while (curNode.next != null) {
19
curNode = curNode.next;
20
++len;
21
}
22
​
23
k %= len;
24
curNode.next = head;
25
​
26
for (int i = 0; i < len - k; i++) {
27
curNode = curNode.next;
28
}
29
​
30
head = curNode.next;
31
curNode.next = null;
32
return head;
33
}
34
}
Copied!

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)
Previous
23 Merge k Sorted Lists
Next
82 Remove Duplicates from Sorted List II
Last modified 2yr ago
Copy link
Contents
61. Rotate List
1. Question
2. Implementation
3. Time & Space Complexity