返回

[Leetcode]143. Reorder List (C++)

题目描述

题目链接:143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

例子

例子 1

Given 1->2->3->4, reorder it to 1->4->2->3.

例子 2

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解题思路

这道题目的思路主要在于怎么从后往前获得节点,通过栈(stack)的先入后出,我们可以获得这个效果:

方法一

利用快慢指针,找到链表的后半段放入栈中,然后利用栈的先进后出原则将节点依次插入前半段中,这里要注意当节点个数为奇数时要保证后半段是较短的,代码如下:

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;

        // find median
        ListNode* fast = head, *slow = head;
        ListNode* tail;
        while (fast && fast->next) {
            fast = fast->next->next;
            tail = slow;
            slow = slow->next;
        }
        if (fast) {
            tail = slow;
            slow = slow->next;
        }
        // cut list into two half
        tail->next = nullptr;

        // push second half list to a stack
        std::stack<ListNode*> second_half;
        while(slow) {
            second_half.push(slow);
            slow = slow->next;
        }

        // concatanate two half
        ListNode* curr = head;
        while (!second_half.empty()){
            ListNode* nextNode = second_half.top();
            second_half.pop();
            nextNode->next = curr->next;
            curr->next = nextNode;
            curr = curr->next->next;
        }

    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

方法二

如果不想找中点,也可以将链表全放入栈中,然后利用链表长度来作为插入完成的指标,同样要注意末尾节点的处理,代码如下:

class Solution {
public:
    void reorderList(ListNode* head) {
        int length = 0;
        ListNode* curr = head;
        std::stack<ListNode*> node_stack;
        while (curr) {
            length++;
            node_stack.push(curr);
            curr = curr->next;
        }

        if (length <= 2) return;

        curr = head;
        int count = 0;
        ListNode* nextNode;
        while (count < length - 1) {
            nextNode = node_stack.top();
            node_stack.pop();

            nextNode->next = curr->next;
            curr->next = nextNode;
            curr = curr->next->next;

            count+= 2;
        }

        if (count == length - 1) {
            curr->next = nullptr;
        } else {
            nextNode->next = nullptr;
        }
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
Built with Hugo
Theme Stack designed by Jimmy