[Swift]LeetCode92.反转链表II|ReverseLinkedListII

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

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

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

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

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

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

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

12ms

 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 reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
14         if head == nil {
15             return nil
16         }
17         
18         let dummy = ListNode(0)
19         dummy.next = head
20         
21         var pre: ListNode? = dummy
22         for _ in 0..<(m - 1) {
23             pre = pre?.next
24         }
25         
26         let start: ListNode? = pre?.next
27         var end: ListNode? = start?.next
28         for _ in 0..<(n - m) {
29             start?.next = end?.next
30             end?.next = pre?.next
31             pre?.next = end
32             end = start?.next
33         }
34         return dummy.next
35     }
36 }

16ms

 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 reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
14         guard head != nil && m < n else {
15             return head
16         }
17         let dummyHead = ListNode(0)
18         dummyHead.next = head
19         var left = dummyHead
20         var end = dummyHead
21         for i in 0..<n {
22             if i == m - 1 {
23                 left = end
24             }
25             end = end.next!
26         }
27         let start = left.next!
28         var newStart = start
29         while newStart !== end {
30             let nextNext = start.next?.next
31             left.next = start.next!
32             start.next!.next = newStart
33             newStart = start.next!
34             start.next = nextNext
35         }
36         return dummyHead.next
37     }
38 }

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 reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
14         if head == nil { return nil }
15         var count = 1
16         var current = head
17         var last: ListNode? = nil //last表示已经反转好的部分链表的头结点
18         var start: ListNode? = nil  //start表示开始反转的节点前一个节点
19         var end: ListNode? = head     //end表示反转部分的最后一个节点
20         while current != nil {
21             if count < m {    
22                 start = current
23                 current = current?.next
24                 end = current
25             } else if count < n + 1 {
26                 var next = current?.next
27                 current?.next = last
28                 last = current
29                 current = next
30             } else {
31                 break
32             }
33             count += 1
34         }
35         end?.next = current
36         start?.next = last
37         if m == 1 {
38             return last
39         } else {
40             return head
41         }
42     }
43 }