返回

[Leetcode]328. Odd Even Linked List(C++)

题目描述

题目链接:328. Odd Even Linked List

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.

例子

例子 1

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

例子 2

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

Constraints

  • 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 …
  • The length of the linked list is between [0, 10^4].

解题思路

这道题要求讲链表中位置为奇数和偶数分别集中重新排列成新的链表,注意不是指节点值而是位置,例如头节点为 1,第二个节点为 2 以此类推。重新排列的方法比较简单,建立两个新的链表头分别指向第一个和第二个节点,然后从第三个节点开始遍历依次插入对应的链表即可。最后要将奇数链表的尾部指向偶数链表的头部,最后很可能漏掉的一步是将偶数链表的尾部指向空节点,如果忘记这一步的话有可能会形成循环链表。

代码如下:

/**
 * 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 || !head->next) {
            return head;
        }

        ListNode* odd_list_head = head;
        ListNode* even_list_head = head->next;

        ListNode* odd_list_tail = odd_list_head;
        ListNode* even_list_tail = even_list_head;

        ListNode* curr = head->next->next;
        int idx = 1;
        while (curr) {
            ListNode* next = curr->next;
            if (idx % 2) {
                odd_list_tail->next = curr;
                odd_list_tail = odd_list_tail->next;
            }
            else {
                even_list_tail->next = curr;
                even_list_tail = even_list_tail->next;
            }

            curr = next;
            idx = idx == 1 ? 0 : 1;
        }
        
        even_list_tail->next = nullptr;
        odd_list_tail->next = even_list_head;
        
        return odd_list_head;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 328.OddEvenLinkedList.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy