C++刷LeetCode（328. 奇偶链表）【链表】

糖逗

题目描述：

1. 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
   
2. 
   
3. 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: 1->2->3->4->5->NULL
   
8. 输出: 1->3->5->2->4->NULL
   
9. 示例 2:
   
10. 
    
11. 输入: 2->1->3->5->6->4->7->NULL
    
12. 输出: 2->3->6->7->1->5->4->NULL
    
13. 说明:
    
14. 
    
15. 应当保持奇数节点和偶数节点的相对顺序。
    
16. 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * struct ListNode {
   
4. *     int val;
   
5. *     ListNode *next;
   
6. *     ListNode() : val(0), next(nullptr) {}
   
7. *     ListNode(int x) : val(x), next(nullptr) {}
   
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   
9. * };
   
10. */
    
11. class Solution {
    
12. public:
    
13.     ListNode* oddEvenList(ListNode* head) {
    
14.         if(head == NULL || head -> next == NULL)return head;  
    
15.         ListNode* temp1 = head, * temp2 = head -> next;
    
16.         ListNode* t1 = temp1, * t2 = temp2;
    
17.         ListNode* temp = t2;
    
18.         ListNode* res = temp1;
    
19.         while(t2 && t2 -> next){//注意这个while里面的判断
    
20.             //奇数位置的链
    
21.             t1 = t1 -> next -> next;
    
22.             temp1 -> next = t1;
    
23.             temp1 = temp1 -> next;
    
24.             //偶数位置的链
    
25.             t2 = t2 -> next -> next;
    
26.             temp2 -> next = t2;
    
27.             temp2 = temp2 -> next;
    
28.         }
    
29.         temp1 -> next = temp;//奇数链和偶数链结合在一起
    
30.         return res;
    
31.     }
    
32. };

复制代码