leetcode 143. 重排链表

重排链表

题目

找出规律。

重排的链表分为两部分
我们将链表的前一部分和后一部分链表。

• 头部节点向后走正序插入
• 尾部节点往后退倒序插入
  两个是交换着互相取出构成新的链。

  分成两部分

  我们可以使用快慢双指针迅速的达到链表的中间。这样就可以将链表分为两部分。

出现的问题
上面看规律也发现是要后一部分是要倒序插入，但是链表是不能后退的。如何实现后一部分的倒序插入呢？

求反链

我们知道使用我们常见的头插法，可以求一个链表的反链。
我们将前半段链表可以，先求一下反链，这一步在使用双指针时，慢指针使用头插法就可以实现
我们将新生成的前半段链表和后半段链表使用头插法，交替插入就可以得到结果

为啥结果是对的？

前一半连续使用了两次头插入，负负的正。和答案的节点顺序时一样的。
后一半本来就是逆序的的，使用了一次头插法，本来是负的，后来加了头插。负负得正。

show your code

class Solution {
public:
    void reorderList(ListNode* head) {

        // 使用快慢 双指针 找到中间节点。并前面半段链表反转。
        // 如果长度是 奇数。那么第一个链先插入。
        if (!head) return;
        ListNode * fast = head->next;
        ListNode * slow = head->next;

        head->next = NULL; // 需要求反链。这是前半段的反链的头节点。
        while (fast && fast->next)
        {
            fast = fast->next->next;
            // 求前面一半反链。头插法
            ListNode * t = slow;
            slow = slow->next;
            t->next=head;
            head = t;
        }

        ListNode * ans = NULL;  // 结果。

        if (!fast){
            // 链表是奇数个。 前一步分比后一部分多一个节点。先插上
            ans = head;
            head = head->next;
            ans->next = NULL;
        }

        while (slow)
        {

            ListNode * t1 = slow->next;
            ListNode * t2 = head->next;
            // 后半段链表使用头插法，生成结果链表
            slow->next = ans;
            ans = slow;

            // 前半段链表使用头插法，生成结果链表
            head->next = ans;
            ans = head;
            // 两个链表分别后移
            slow = t1;
            head = t2;

        }
        head = ans;
    }
};