(链表专题) 328. 奇偶链表 ——【Leetcode每日一题】

叁歲伎倆 2024-03-23 09:57 67阅读 0赞

### 328. 奇偶链表 ###

给定单链表的头节点 `head` ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

**第一个** 节点的索引被认为是 **奇数** ， **第二个** 节点的索引为 **偶数** ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 `O(1)` 的额外空间复杂度和 `O(n)` 的时间复杂度下解决这个问题。

##### 示例 1: #####

![在这里插入图片描述][3453c0c08b524f48a7a24b6816c0806a.png]

> 输入: head = \[1,2,3,4,5\]  
> 输出: \[1,3,5,2,4\]

##### 示例 2: #####

![在这里插入图片描述][7d5e5572b4e84b2a89ce28cd7b98ec45.png]

> 输入: head = \[2,1,3,5,6,4,7\]  
> 输出: \[2,3,6,7,1,5,4\]

**提示:**

*  n == 链表中的节点数
 *   0 < = n < = 1 0 4 0 <= n <= 10^4 0<=n<=104
 *   − 1 0 6 < = N o d e . v a l < = 1 0 6 -10^6 <= Node.val <= 10^6 −106<=Node.val<=106

#### 思路： ####

*  分别定义奇偶链表，头节点分别为：`head` 和 `head2`；
 *  再定义两个节点 `odd` , `even` 分别定义指向奇链表和偶链表最后一个节点
 *  遍历原链表，将当前结点 **交替** 插入到奇链表和偶链表（**尾插法**）；
 *  将偶链表拼接在奇链表后面。

#### 代码：(Java、C++) ####

**Java**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if(head == null || head.next == null) return head;
            ListNode head2 = head.next;//偶链表头节点
            ListNode odd = head, even = head2;//分别定义指向奇链表和偶链表最后一个节点
            while(even != null && even.next != null){
        
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = head2;
            return head; 
        }
    }

**C++**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
    class Solution {
        
    public:
        ListNode* oddEvenList(ListNode* head) {
        
            if(head == NULL || head->next == NULL) return head;
            ListNode* head2 = head->next;//偶链表头节点
            ListNode* odd = head, *even = head2;//分别定义指向奇链表和偶链表最后一个节点
            while(even != NULL && even->next != NULL){
        
                odd->next = even->next;
                odd = odd->next;
                even->next = odd->next;
                even = even->next;
            }
            odd->next = head2;
            return head; 
        }
    };

##### 运行结果： #####

![在这里插入图片描述][e22f43aef4e748039055e4905bbe4495.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是链表的节点数。需要遍历链表中的每个节点，并更新指针。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)。只需要维护有限的指针。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[3453c0c08b524f48a7a24b6816c0806a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/7f7ab722a8894c2d80796bba38f1d0c2.png
[7d5e5572b4e84b2a89ce28cd7b98ec45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/30cb82f8d26a456aacc602369b1fc6f2.png
[e22f43aef4e748039055e4905bbe4495.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/516cb37c470b4ac18af8ae28ad3b66d6.png
[Link 1]: https://leetcode.cn/problems/odd-even-linked-list/description/
[leetCode]: http://t.csdn.cn/kQLJO