本文共 1964 字，大约阅读时间需要 6 分钟。

题目描述

解题思路

• 我们知道ArrayList的底层就是用数组实现的，所以我们将链表储存在一个ArrayList中，然后利用双指针，一个指向最前面，一个指向最后面，依次访问并向题目要求的链表形式进行转换！

public void reorderList_1(ListNode head) {           if (head == null){               return;        }        List
   
     list = new ArrayList<>(); //ArrayList为线性表        //将链表的每一个节点依次存进ArrayList中        while (head != null){               list.add(head);            head = head.next;        }        //两个之正依次向前，后进行遍历取元素        int i = 0,j = list.size() - 1;        while (i < j){               //1->2->3->4            //前面的节点的下一个节点指向最后的节点            list.get(i).next = list.get(j);  //1->4            i++;  //此时i++ ,则此时list.get(i)为原来前面节点的下一个节点  即节点2            if(i == j)  //若链表长度为偶数的情况下，则会提前相遇，则终止循环                break;            list.get(j).next = list.get(i);  // 4->2            //此时变为 1->4->2->            j--;        }        list.get(i).next = null; // 最后一个节点的下一个节点为null    }
   

• 三步走：1. 将链表分为两个链表 2. 将第二个链表逆序 3. 依次连接两个链表

public void reorderList(ListNode head){           if (head == null || head.next == null || head.next.next == null)            return;        ListNode slow = head;        ListNode fast = head.next;        while (fast != null && fast.next != null){               slow = slow.next;            fast = fast.next.next;        }        ListNode mid = slow.next;        slow.next = null;  //将链表一分为二        ListNode newHead = reverse(mid);    //反转链表        while (newHead != null){     //反转后将两个链表进行合并            ListNode temp = newHead.next;            newHead.next = head.next;            head.next = newHead;            head = newHead.next;            newHead = temp;        }    }    private ListNode reverse(ListNode head) {           if (head == null)            return head;        ListNode tail = head;        head = head.next;        tail.next = null;        while (head != null){               ListNode tmp = head.next;            head.next = tail;            tail = head;            head = tmp;        }        return tail;    }