leetcode 143 --reorder list

图片.png

• 基本思路：分为三部分：

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。ListNode* findMid(ListNode* head) 这个函数主题没什么可说的很简单。常规快慢指针。

2. 将第二个链翻转。ListNode* reverse(ListNode* head) {//一定会返回一个新的头节点。这个需要注意的是我只需要有一个新的头节点，每次都更新头节点的位置 最后返回新的头节点就可以完成。

3. 将第二个链表的元素间隔地插入第一个链表中。

• 具体实现过程的两个链表：

  
  图片.png

C++:

//my
    ListNode* findMid(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr&& fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head) {//一定会返回一个新的头节点
        ListNode* newnew = nullptr;
        while (head != nullptr) {
            ListNode* tt = head->next;
            head->next = newnew;
            newnew = head;
            head = tt;
        }
        return newnew;
    }
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next)
            return;
        ListNode* mid = findMid(head);
        ListNode* t2 = mid->next;
        t2 = reverse(t2);
        mid->next = nullptr;

        ListNode* t1 = head;
        while (t1 != nullptr&& t2 != nullptr) {
            ListNode* nn = t1->next;
            t1->next = t2;
            t2 = t2->next;
            t1->next->next = nn;
            t1 = nn;
        }
    }

JAVA：

public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null&& fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head) {//一定会返回一个新的头节点
        ListNode newnew = null;
        while (head != null) {
            ListNode tt = head.next;
            head.next = newnew;
            newnew = head;
            head = tt;
        }
        return newnew;
    }
    public void reorderList(ListNode head) {
        if (head==null)
            return;
        ListNode mid = findMid(head);
        ListNode t2 = mid.next;
        t2 = reverse(t2);
        mid.next = null;

        ListNode t1 = head;
        while (t1 != null&& t2 != null) {
            ListNode nn = t1.next;
            t1.next = t2;
            t2 = t2.next;
            t1.next.next = nn;
            t1 = nn;
        }
    }