[Swift]LeetCode61.旋转链表|RotateList

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9920940.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

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

20ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
14         // Count length
15         var l = 0
16         var p = head
17         var last = p
18         while p != nil {
19             l += 1
20             last = p
21             p = p!.next
22         }
23         
24         if l == 0 { return head }
25         
26         // Rotate
27         let dummyHead = ListNode(0)
28         dummyHead.next = head
29         p = dummyHead
30         for _ in 0..<(l - k % l) % l {
31             p = p!.next
32         }
33         let ret = p!.next
34         p!.next = nil
35         last!.next = dummyHead.next
36         return ret
37     }
38 }

24ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
14         if(head?.next == nil || k == 0){
15             return head
16         }
17         var current = head
18         var array = [Int]()
19         var n = 0
20         while(current != nil){
21             array.append(current!.val)
22             n += 1
23             current = current!.next  
24         }
25         var preHead = ListNode(0)
26         current = preHead
27         var start = (n - (k % n)) % n
28         for i in start ..< (start + n){
29             var newNode = ListNode(array[(i % n)])
30             current!.next = newNode
31             current = current!.next
32         }
33         return preHead.next  
34     }
35 }

28ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
14         if head == nil || head?.next == nil || k == 0 {
15             return head
16         }
17         var (fastPtr, slowPtr, length) = (head, head, 1)
18         while let _ = fastPtr?.next {   // get list length
19             length += 1
20             fastPtr = fastPtr?.next
21         }
22         
23         let slowLenth = length - k%length
24         for _ in 1..<slowLenth {       // how many steps slowPtr needs to go
25             slowPtr = slowPtr?.next
26         }
27         
28         fastPtr?.next = head            // perform rotation
29         let newHead = slowPtr?.next
30         slowPtr?.next = nil
31         
32         return newHead;
33     }
34 }

28ms

 1 class Solution {
 2     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
 3         guard let head = head else {
 4             return nil
 5         }
 6         var newHeadNode: ListNode! = head;
 7         var newTailNode: ListNode! = head;
 8         var tailNode: ListNode! = head;
 9         var linkLength = 1;
10         while tailNode.next != nil {
11             tailNode = tailNode.next;
12             linkLength += 1
13         }
14         if linkLength <= 1 {
15             return head;
16         }
17         let k = k % linkLength
18         for _ in 0 ..< abs(linkLength - k - 1)  {
19             if newTailNode.next != nil {
20                 newTailNode = newTailNode.next
21             } else {
22                 newTailNode = head
23             }
24         }
25         if newTailNode.next != nil {
26             newHeadNode = newTailNode.next
27             tailNode.next = head;
28             newTailNode.next = nil;
29             return newHeadNode;
30         } else {
31             return head;
32         }
33     }
34 }

40ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
14         /*
15          *  思路,首先我们计算出链表的长度,这样据k值可以计算出链表实际移动距离
16          *  然后,通过两个指针来记录移动位置
17          */
18         var length = 0
19         var temp = head
20         while temp?.next != nil {
21             length += 1
22             temp = temp?.next
23         }
24         
25         // 长度已经获取length+1
26         let stride = k % (length + 1)
27         if stride == 0{
28             return head
29         }
30         // stride为实际需要移动的距离
31         // 定义两个指针,一个指向链表倒数第stride+1个,一个指向最后一个
32         var start: ListNode?
33         var end: ListNode?
34         var tem: ListNode?
35         for index in 0...length{
36             if index == 0 {
37                 tem = head
38                 end = head
39             }else{
40                 tem = tem?.next
41                 end = end?.next
42             }
43             if index == length + 1 - (stride + 1) {
44                 start = tem
45             }
46         }
47         
48         /*
49          *  修改节点
50          */
51         let res = start?.next
52         start?.next = nil
53         end?.next = head
54         
55         return res
56     }
57 }

48ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
14         guard let head = head else {
15             return nil
16         }
17 
18         guard k > 0 else {
19             return head
20         }
21 
22         var length = 0
23         var next: ListNode? = head
24         var tail = head
25         while next != nil {
26             tail = next!
27             next = next?.next
28             length += 1
29         }
30         
31         if (length == 1) {
32             return head
33         }
34 
35         let k = k > length ? k % length : k
36         if (k == length || k == 0) {
37             return head
38         }
39         
40         next = head
41         for _ in 0..<length - k - 1 {
42             next = next?.next
43         }
44         let start = next?.next
45         tail.next = head
46         next?.next = nil
47         return start
48     }
49 }