題目描述
給定單鏈表的頭節(jié)點 head 硝枉，將所有索引為奇數(shù)的節(jié)點和索引為偶數(shù)的節(jié)點分別組合在一起妻味，然后返回重新排序的列表责球。
第一個節(jié)點的索引被認為是 奇數(shù) 雏逾， 第二個節(jié)點的索引為 偶數(shù) 栖博，以此類推仇让。
請注意躺翻，偶數(shù)組和奇數(shù)組內部的相對順序應該與輸入時保持一致获枝。
你必須在 O(1) 的額外空間復雜度和 O(n) 的時間復雜度下解決這個問題
示例1:
輸入: head = [1,2,3,4,5]
輸出: [1,3,5,2,4]
示例2:
輸入: head = [2,1,3,5,6,4,7]
輸出: [2,3,6,7,1,5,4]
題解
對于原始鏈表省店，每個節(jié)點都是奇數(shù)節(jié)點或偶數(shù)節(jié)點懦傍。頭節(jié)點是奇數(shù)節(jié)點粗俱，頭節(jié)點的后一個節(jié)點是偶數(shù)節(jié)點寸认，相鄰節(jié)點的奇偶性不同。因此可以將奇數(shù)節(jié)點和偶數(shù)節(jié)點分離成奇數(shù)鏈表和偶數(shù)鏈表唱蒸，然后將偶數(shù)鏈表連接在奇數(shù)鏈表之后神汹，合并后的鏈表即為結果鏈表
思路1:
原始鏈表的頭節(jié)點 head 也是奇數(shù)鏈表的頭節(jié)點以及結果鏈表的頭節(jié)點屁魏，head 的后一個節(jié)點是偶數(shù)鏈表的頭節(jié)點氓拼。令 evenHead = head.next披诗，則 evenHead 是偶數(shù)鏈表的頭節(jié)點立磁。
維護兩個指針 odd 和 even 分別指向奇數(shù)節(jié)點和偶數(shù)節(jié)點宪摧，初始時 odd = head几于，even = evenHead沿后。通過迭代的方式將奇數(shù)節(jié)點和偶數(shù)節(jié)點分離成兩個鏈表尖滚，每一步首先更新奇數(shù)節(jié)點睦裳，然后更新偶數(shù)節(jié)點。
更新奇數(shù)節(jié)點時撼唾，奇數(shù)節(jié)點的后一個節(jié)點需要指向偶數(shù)節(jié)點的后一個節(jié)點廉邑，因此令 odd.next = even.next，然后令 odd = odd.next，此時 odd 變成 even 的后一個節(jié)點蛛蒙。
更新偶數(shù)節(jié)點時糙箍，偶數(shù)節(jié)點的后一個節(jié)點需要指向奇數(shù)節(jié)點的后一個節(jié)點，因此令 even.next = odd.next牵祟，然后令 even = even.next倍靡，此時 even 變成 odd 的后一個節(jié)點。
在上述操作之后课舍，即完成了對一個奇數(shù)節(jié)點和一個偶數(shù)節(jié)點的分離塌西。重復上述操作，直到全部節(jié)點分離完畢筝尾。全部節(jié)點分離完畢的條件是 even 為空節(jié)點或者 even.next 為空節(jié)點，此時 odd 指向最后一個奇數(shù)節(jié)點（即奇數(shù)鏈表的最后一個節(jié)點）。
最后令 odd.next = evenHead，將偶數(shù)鏈表連接在奇數(shù)鏈表之后汰蓉，即完成了奇數(shù)鏈表和偶數(shù)鏈表的合并，結果鏈表的頭節(jié)點仍然是 head
// OC
+ (ListNode *)oddEvenList1:(ListNode *)head {
ListNode *odd = head;
ListNode *evenHead = head.next;
ListNode *even = head.next;
while (even != nil && even.next != nil) {
// 奇數(shù)節(jié)點的下一個節(jié)點指向偶數(shù)節(jié)點的next
odd.next = even.next;
// odd 變成 even 的后一個節(jié)點
odd = odd.next;
// 偶數(shù)節(jié)點的下一個節(jié)點指向奇數(shù)節(jié)點的next
even.next = odd.next;
// even 變成 odd 的后一個節(jié)點
even = even.next;
}
odd.next = evenHead;
return head;
}
// Swift
static public func oddEvenList1(_ head:ListNode?) -> ListNode? {
if head == nil {
return head
}
// 偶數(shù)鏈表的頭節(jié)點
let evenHead = head?.next
var odd = head
var even = head?.next
while even != nil && even?.next != nil {
// 奇數(shù)節(jié)點的后一個節(jié)點需要指向偶數(shù)節(jié)點的后一個節(jié)點
odd?.next = even?.next
// odd 變成 even 的后一個節(jié)點
odd = odd?.next
// 偶數(shù)節(jié)點的后一個節(jié)點需要指向奇數(shù)節(jié)點的后一個節(jié)點
even?.next = odd?.next
// even 變成 odd 的后一個節(jié)點
even = even?.next
}
odd?.next = evenHead
return head
}
思路2:
令evenHeadNode = head?.next 則 evenHeadNode 為偶數(shù)鏈表的頭節(jié)點灾常，oddTailNode為奇數(shù)鏈表的尾部節(jié)點
遍歷所有節(jié)點，奇數(shù)節(jié)點的Next指向下一個奇數(shù)節(jié)點，偶數(shù)節(jié)點的Next指向下一個偶數(shù)節(jié)點，即curNode?.next = curNode?.next?.next，并且判斷當前奇數(shù)鏈表是否遍歷完成落剪，如果奇數(shù)節(jié)點便利結束凡泣，則令oddTailNode = curNode
在遍歷結束后，合并奇數(shù)鏈表和偶數(shù)鏈表，即oddTailNode?.next = evenHeadNode
// OC
+ (ListNode *)oddEvenList2:(ListNode *)head {
// 記錄偶數(shù)鏈表的頭部
ListNode *evenHeadNode = head.next;
// 記錄奇數(shù)鏈表的尾部
ListNode *oddTailNode = nil;
ListNode *curNode = head;
// 奇偶 true為奇數(shù)，false偶數(shù)
BOOL flag = YES;
while (curNode != nil) {
if (flag && (curNode.next == nil || curNode.next.next == nil)) {
oddTailNode = curNode;
}
ListNode *nextNode = curNode.next;
curNode.next = curNode.next.next;
curNode = nextNode;
flag = !flag;
}
oddTailNode.next = evenHeadNode;
return head;
}
// Swift
static public func oddEvenList2(_ head:ListNode?) -> ListNode? {
if head == nil {
return head
}
var curNode = head
// 記錄偶數(shù)鏈表的頭部
let evenHeadNode = head?.next
// 記錄奇數(shù)鏈表的尾部
var oddTailNode:ListNode?
// 奇偶 true為奇數(shù)项阴，false偶數(shù)
var flag:Bool = true
while(curNode != nil) {
if flag && (curNode?.next == nil || curNode?.next?.next == nil) {
// 奇數(shù)鏈表 循環(huán)完畢
oddTailNode = curNode
}
// 下次遍歷節(jié)點
let nextNode = curNode?.next
// curNode?.next = curNode?.next?.next
// 當前節(jié)點的next指向當前節(jié)點的Next的Next
curNode?.next = curNode?.next?.next
curNode = nextNode
flag = !flag
}
oddTailNode?.next = evenHeadNode
return head
}
參考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvdwtj/
https://leetcode-cn.com/problems/odd-even-linked-list/solution/qi-ou-lian-biao-by-leetcode-solution/
