[Swift]LeetCode328.奇偶链表|OddEvenLinkedList

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

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

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

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

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

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

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

36ms

 1 class Solution {
 2     func oddEvenList(_ head: ListNode?) -> ListNode? {
 3         let dummy = ListNode(0)
 4         var node = head
 5         var next = head?.next
 6         var oddEnd: ListNode?
 7         let evenHead = head?.next
 8         dummy.next = node
 9         var isOdd = true
10         while node != nil {
11             node?.next = node?.next?.next
12             if isOdd {
13                 oddEnd = node
14             }
15             node = next
16             next = next?.next
17             isOdd = !isOdd
18         }
19         oddEnd?.next = evenHead
20         return dummy.next
21     }
22 }

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 oddEvenList(_ head: ListNode?) -> ListNode? {
14         var odd: ListNode? = head
15         var even: ListNode? = head?.next
16         var evenFirst: ListNode? = even
17         
18         while true {
19             if odd == nil || even == nil || even?.next == nil {
20                 odd?.next = evenFirst
21                 break
22             }
23             
24             // Connecting odd
25             odd?.next = even?.next
26             odd = even?.next
27             
28             if odd?.next == nil {
29                 even?.next = nil
30                 odd?.next = evenFirst
31                 break
32             }
33             
34             // Connection even
35             even?.next = odd?.next
36             even = even?.next
37             
38         }
39         
40         return head
41     }
42 }

44ms

 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 oddEvenList(_ head: ListNode?) -> ListNode? {
14         var oddNode = head?.next?.next
15         var evenNode = head?.next
16         let evenHeadNode = head?.next
17         var node = head
18         while oddNode != nil {
19             evenNode?.next = oddNode?.next
20             node?.next = oddNode
21             oddNode?.next = evenHeadNode
22             node = oddNode
23             evenNode = evenNode?.next
24             oddNode = evenNode?.next
25         }
26         
27         return head
28     }
29 }

56ms

 1 class Solution {
 2     func oddEvenList(_ head: ListNode?) -> ListNode? {
 3         let dummy = ListNode(0)
 4         let dummyOdd = ListNode(0)
 5         dummy.next = head
 6         var cur = head
 7         var curOdd = head?.next
 8         var index = 1
 9         dummyOdd.next = curOdd
10         while cur?.next != nil  && curOdd?.next != nil{
11             if index % 2 == 1 {
12                 cur?.next = curOdd?.next
13                 cur = cur?.next
14             }else {
15                 curOdd?.next = cur?.next
16                 curOdd = curOdd?.next
17             }
18             index += 1
19         }
20         cur?.next = dummyOdd.next
21         curOdd?.next = nil
22         return dummy.next
23     }
24 }

64ms

 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 oddEvenList(_ head: ListNode?) -> ListNode? {
14         var i = head
15         var j = head?.next
16         let jH = j
17         
18         while i?.next?.next != nil || j?.next?.next != nil {
19             if i?.next?.next != nil {
20                 i?.next = i?.next?.next
21                 i = i?.next
22             }
23             if j?.next?.next != nil {
24                 j?.next = j?.next?.next
25                 j = j?.next
26             }
27         }
28         j?.next = nil // 清空偶数节点的next
29         i?.next = jH
30         return head
31     }
32 }

92ms

 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 oddEvenList(_ head: ListNode?) -> ListNode? {
14         var first = head
15         var second = head?.next
16         let doulbeNode = second
17         var lastCNode = head
18         while first != nil || second != nil {
19             first?.next = second?.next
20             lastCNode = first
21             first = first?.next
22             second?.next = first?.next
23             second = second?.next
24         }
25         lastCNode?.next = doulbeNode
26         return head
27     }
28 }