[LeetCode] 143. 重排链表

[Animenzzzz]

题目描述：

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解题思路：先使用快慢指针，将链表从中间截断。后面的那一段，逆序。之后两个链表再进行拼接即可。

C++解题：

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next) return;
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *mid = slow->next;
        slow->next = NULL;
        ListNode* pre = NULL,*last = mid;
        while (last)
        {
            ListNode *next = last->next;
            last->next = pre;
            pre = last;
            last = next;
        }
        while (head && pre){
            ListNode* head_next = head->next;
            ListNode* pre_next = pre->next;
            head->next = pre;
            pre->next = head_next;
            head = head_next;
            pre = pre_next;
        }
    }
};