143. Reorder List.md

143. Reorder List

思路

仔细分析题意可将整个解法分成三个部分:

1. 找到链表中点位置(可用快慢指针实现), 并将链表从中点处断开，形成两个独立的链表;
2. 翻转第二个链表;
3. 将第二个链表的元素间隔地插入第一个链表中。

改进

上面的空间复杂度为O(1), 其实可以牺牲一下空间复杂度来加快速度: 用一个栈来存放后半部分节点, 这样就可以不用翻转链表而直接进行拼接了.

C++

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast -> next){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        if(slow == fast) return; // 不到三个节点
        
        // 翻转链表的后半部分
        ListNode *tmp1 = slow -> next, *tmp2;
        slow -> next = NULL;
        while(tmp1){
            tmp2 = tmp1 -> next;
            tmp1 -> next = slow -> next;
            slow -> next = tmp1;
            tmp1 = tmp2;
        }

        ListNode *p1 = head, *p2 = slow -> next;
        slow -> next = NULL;
        while(p2){
            tmp1 = p1 -> next;
            tmp2 = p2 -> next;
            p1 -> next = p2;
            p2 -> next = tmp1;
            
            p1 = p2 -> next;
            p2 = tmp2;
        }
    }
};

改进

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast -> next){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        if(slow == fast) return; // 不到三个节点
        
        // 用一个栈存放后半部分
        stack<ListNode *>stk;
        ListNode *tmp1 = slow -> next;
        slow -> next = NULL;
        while(tmp1){
            stk.push(tmp1);
            tmp1 = tmp1 -> next;
        }

        ListNode *p1 = head, *p2;
        while(!stk.empty()){
            p2 = stk.top();
            stk.pop();
            
            tmp1 = p1 -> next;
            p1 -> next = p2;
            p2 -> next = tmp1;
            
            p1 = tmp1;
        }
    }
};