Given a singly linked list L : L 0→L 1→…→L**n -1→L n,L 0→L**n →L 1→L**n -1→L 2→L**n -2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example 1:
1 Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
1 Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
思路： 思路一：暴力解法 直接将链表存在数组中，然后进行操作，不用考虑断链等问题，直接用数组下标解决一切
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public void reorderList (ListNode head) if (head == null ) return ; List<ListNode> list = new ArrayList<>(); while (head != null ) { list.add(head); head = head.next; } int i = 0 , j = list.size() - 1 ; while (i < j) { list.get(i).next = list.get(j); i++; if (i == j) { break ; } list.get(j).next = list.get(i); j--; } list.get(j).next = null ; }
时间复杂度：O(n)
空间复杂度：O(n)
思路二：递归 看到递归还是要想到两个方面的问题：
首先要明确递归传出来的是啥，为什么使用思路一的想法就是，我想找最后一个元素，但是每次都要遍历一遍才能找到那个元素，所以使用了数组，通过下标获取其中的元素。所以，我们应该递归出来的局部链表的尾元素，看下面的🌰：
现在递归到出口，那么我们应该将 tail 传出来
第二，本题的出口要分为两种情况：奇数个和偶数
奇数：直接传出来
偶数：将它的 next 传出来
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public void reorderList (ListNode head) if (head == null || head.next == null ) return ; int len = 0 ; ListNode count = head; while (count != null ) { count = count.next; len++; } helper(head, len); } private ListNode helper (ListNode listNode, int length) if (length == 1 ) { ListNode tail = listNode.next; listNode.next = null ; return tail; } if (length == 2 ) { ListNode tail = listNode.next.next; listNode.next.next = null ; return tail; } ListNode helper = helper(listNode.next, length - 2 ); ListNode cur = listNode.next; ListNode next = helper.next; listNode.next = helper; helper.next = cur; return next; }
思路三：分组解法 还可以将这个题分为以下几个部分：
找到中点，分割成两个链表
对后一个链表进行逆序
双指针同步进行，将后面链表与前面的链表进行连接
1 2 3 4 5 6 7 8 1 -> 2 -> 3 -> 4 -> 5 -> 6 分割：1 -> 2 -> 3 4 -> 5 -> 6 逆序：6 -> 5 -> 4 连接：1 -> 6 -> 2 -> 5 -> 3 -> 4
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 public void reorderList (ListNode head) if (head == null || head.next == null ) return ; ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null ) { slow = slow.next; fast = fast.next.next; } ListNode cur = slow.next; slow.next = null ; ListNode next = reverseList(cur); while (head != null && next != null ) { ListNode l1 = head.next; ListNode l2 = next.next; head.next = next; next.next = l1; head = l1; next = l2; } } private ListNode reverseList (ListNode head) if (head == null || head.next == null ) { return head; } ListNode listNode = reverseList(head.next); head.next.next = head; head.next = null ; return listNode; }
时间复杂度：O(n)
空间复杂度：O(1)
注：在 LeetCode 中，递归法时间复杂度可以 beats 100%，第三种方法不可以，按照分析来说，应该是一样的
